堆的原理和实现

什么是堆

堆满足下面两点：

• 是一颗完全二叉树
• 大顶堆任意孩子节点小于或等于父节点(小顶堆任意孩子节点大于或等于父节点)

先来看几张图。

图1

图2

图3

上面几张图中，图1不满足完全二叉树的性质，图2是合格的最大堆，图3不满足孩子节点小于或等于父节点的性质。

堆的用途

优先队列指的是元素入队和出队的顺序与时间无关，既不是先进先出，也不是先进后出，而是根据元素的重要性来决定的。
例如，操作系统的任务执行是优先队列。一些情况下，会有新的任务进入，并且之前任务的重要性也会改变或者之前的任务被完成出队。而这个出队、入队的过程利用堆结构，时间复杂度是O($x^2$)。
注意：堆有很多种实现左式堆、斜堆、斐波那锲堆、二叉堆、三叉堆、N叉堆等。由于二叉堆使用很广泛，本文讨论的都是二叉堆。

堆的存储结构

由于数组占用的是连续的内存空间，相对来说对于散列存储的结构来说，数组可以节省连续的内存空间，不会将内存打乱，所以一般用数组存储堆的节点。

图4 从数组下标0开始存储堆 图4是从数组下标0开始表示堆，可以看出对于堆中的父子节点关系：leftChild=2 * parent(i)+1、rightChild=2 * parent(i)+2、parent=(child(i)-1)/2。

图5 从数组下标1开始存储堆 图5是从数组下标1开始表示堆，可以看出对于堆中的父子节点关系：leftChild=2 * parent(i)、rightChild=2 * parent(i)+1、parent=child(i)/2。

一般情况下不选用下标为0的位置来存储数据，下标为0的位置通常使用一个很大的数字或者很小的数字作为哨兵变量,从下标1开始也能更方便地表示父子节点关系。本文后续的代码实现也是从1开始存储。

堆的基本操作(Java实现)

建堆

思路是将待建堆的数组当成一颗完全二叉树，然后从最后一个非叶子节点开始，和其孩子节点比较，依次向前循环非叶子节点保证堆序性，这个过程叫做下滤(percolate down)。从其存储结构知道parent=child(i)/2,那么最后一个非叶子节点=堆的大小/2。我们定义一个建堆数组和堆的大小，如下所示：

int[]  arr = {-1,19,20,32,5,45,6,8,9,15,1};  //-1为哨兵变量
int currentSize = arr.length - 1;//记录堆的大小，注意扩容操作

初始的完全二叉树如图6所示：

图6

进行percolateDown(5)后如图7所示：

图7

进行percolateDown(4)后如图8所示：

图8

进行percolateDown(3)后如图9所示：

图9

进行percolateDown(2)后如图10所示：

图10

进行percolateDown(1)后如图11所示：

图11

这样一个二叉大顶堆就建好了。下滤操作的代码如下所示：

/**
  * 下滤操作
  * 保证每个非叶子节点都比其左右孩子大
  * @param i 待调整的节点(非叶子节点)
  * @param currentSize 堆的大小
  */
 private void percolateDown(int i, int currentSize) {
     int leftChild = i*2;
     int rightChild = leftChild+1;
     // 如果没有左孩子（越界），直接返回
     if (leftChild > currentSize) return;
     // 在左孩子与要调整的节点中找到最大的下标
     int maxIndex = arr[i] > arr[leftChild] ? i : leftChild;
     // 如果存在右孩子，在刚刚找到的最大的下标和右孩子中找最大的下标
     if (rightChild <= currentSize) maxIndex = arr[maxIndex] > arr[rightChild] ? maxIndex : rightChild;
     // 如果要调整的节点已经是最大的了，说明顺序正确，直接返回
     if (maxIndex == i) return;
     // 执行交换
     swapReferences(i, maxIndex);
     // 递归调整
     percolateDown(maxIndex, currentSize);
 }

建堆操作的代码如下所示：

for (int i = currentSize / 2; i >= 1; i--)
    percolateDown(i, currentSize);

删除堆顶元素

删除堆顶元素思路是用最后一个元素替换掉堆顶元素，堆的大小减1，再执行下滤(percolate down)操作调整。上面建好的堆删掉堆顶元素流程如下所示：
第一步，用最后一个元素替换堆，堆的大小减1。

图12

第二步执行下滤操作，如图13-图14所示。

图13

图14 这样顶部元素45就删除完成了。相关代码如下所示：

// 用最后一个元素覆盖掉顶部的元素->堆元素个数减去1->执行下滤操作
arr[1] = arr[currentSize--];
percolateDown(1,currentSize);

插入

往堆中插入元素的思路是先把元素放到堆尾，然后循环和父节点比较大小，直到父节点比其大，这个过程叫做上滤(percolate up)。例如在上面的堆中插入50的过程如下所示：
第一步，把50放入堆尾，如图15所示。

图15

第二步，执行上滤操作，如图16-18所示。

图16 执行上滤操作

图17 执行上滤操作

图18 执行上滤操作 上滤操作代码如下：

/**
 * 上滤操作
 * 把每个叶子节点与其父节点进行比较，直到越界或者其父节点更大
 * @param i
 */
private void percolateUp(int i){
    int parent = i/2;
    if(parent < 1) return;
    if(arr[i] > arr[parent]){
        swapReferences(i,parent);
        percolateUp(parent);
    }
}

插入操作代码如下：

/**
 * 堆操作：插入
 * 把元素插入到最后，然后递归执行上滤操作
 * @param x
 */
private void insert(int x){
    // 扩容
    if( currentSize == arr.length - 1 )
        enlargeArray(currentSize*2);
    arr[++currentSize]=x;
    percolateUp(currentSize);
}

完整源码

package com.test;

import java.util.Arrays;

public class Heap {

 int[]  arr = {-1,19,20,32,5,45,6,8,9,15,1};  //-1为哨兵变量
 int currentSize = arr.length - 1;//记录堆的大小，注意扩容操作

 public static void main(String[] args) {
     Heap heap = new Heap();
     heap.bulidHeap();
 }

 /**
  * 堆操作：建立一个大顶堆
  * 从最后一个非叶子节点开始向前循环执行下滤操作
  */
 private void bulidHeap() {
     for (int i = currentSize / 2; i >= 1; i--)
         percolateDown(i, currentSize);
     System.out.println("建堆后结果：" + Arrays.toString(arr));
     System.out.println("当前堆大小："+currentSize);
 }

 /**
  * 下滤操作
  * 保证每个非叶子节点都比其左右孩子大
  * @param i 待调整的节点(非叶子节点)
  * @param currentSize 堆的大小
  */
 private void percolateDown(int i, int currentSize) {
     int leftChild = i*2;
     int rightChild = leftChild+1;
     // 如果没有左孩子（越界），直接返回
     if (leftChild > currentSize) return;
     // 在左孩子与要调整的节点中找到最大的下标
     int maxIndex = arr[i] > arr[leftChild] ? i : leftChild;
     // 如果存在右孩子，在刚刚找到的最大的下标和右孩子中找最大的下标
     if (rightChild <= currentSize) maxIndex = arr[maxIndex] > arr[rightChild] ? maxIndex : rightChild;
     // 如果要调整的节点已经是最大的了，说明顺序正确，直接返回
     if (maxIndex == i) return;
     // 执行交换
     swapReferences(i, maxIndex);
     // 递归调整
     percolateDown(maxIndex, currentSize);
 }

 /**
  * 交换数组元素
  * @param j 数组下标
  * @param i 数组下标
  */
 private void swapReferences(int j, int i) {
     int tmp = arr[j];
     arr[j] = arr[i];
     arr[i] = tmp;
 }

 /**
  *  堆操作：删除堆顶元素
  * 用最后一个元素覆盖掉顶部的元素->堆元素个数减去1->执行下滤操作
  * @return
  */
 private int deleteMax(){
     if(isEmpty()){
         System.out.println("当前堆已为空，不能删除！");
         return 0;
     }
     int max = arr[1];
     // 用最后一个元素覆盖掉顶部的元素->堆元素个数减去1->执行下滤操作
     arr[1] = arr[currentSize--];
     percolateDown(1,currentSize);

     arr = Arrays.copyOf(arr, currentSize+1);
     System.out.println("删除堆顶后结果：" + Arrays.toString(arr));
     System.out.println("当前堆大小："+currentSize);
     return max;
 }

 /**
  * 判空
  * 如果堆大小为0返回真
  * @return
  */
 private boolean isEmpty( )
 {
     return currentSize == 0;
 }

 /**
  * 堆操作：插入
  * 把元素插入到最后，然后递归执行上滤操作
  * @param x
  */
 private void insert(int x){
     // 扩容
     if( currentSize == arr.length - 1 )
         enlargeArray(currentSize*2);
     arr[++currentSize]=x;
     percolateUp(currentSize);
     System.out.println("插入"+x+"后结果：" + Arrays.toString(arr));
     System.out.println("当前堆大小："+currentSize);
 }

 /**
  * 扩容
  * @param newSize 新大小
  */
 private void enlargeArray(int newSize) {
     int [] old = arr;
     arr = new int[newSize];
     for( int i = 0; i<old.length; i++ )
         arr[i] = old[i];
 }

 /**
  * 上滤操作
  * 把每个叶子节点与其父节点进行比较，直到越界或者其父节点更大
  * @param i
  */
 private void percolateUp(int i){
     int parent = i/2;
     if(parent < 1) return;
     if(arr[i] > arr[parent]){
         swapReferences(i,parent);
         percolateUp(parent);
     }
 }
}

运行结果如下所示：

建堆后结果：[-1, 45, 20, 32, 15, 19, 6, 8, 9, 5, 1]
当前堆大小：10
删除堆顶后结果：[-1, 32, 20, 8, 15, 19, 6, 1, 9, 5]
当前堆大小：9
插入50后结果：[-1, 50, 32, 8, 15, 20, 6, 1, 9, 5, 19, 0, 0, 0, 0, 0, 0, 0]
当前堆大小：10