二叉堆建堆的优化算法原理图解及代码实现

二叉堆的简单建堆方法

有时二叉堆是由一些项的初始结合构造而得。这种构造方法以N项作为输入。
最浅显的建堆方式，可以通过N个连续的insert操作（Williams’ method）来完成，由于每个insert将花费O(logN)时间，因此建堆的最坏运行时间是O(NlogN)。但是这种建堆的方式并不是最优算法。

二叉堆的优化建堆方法

更快速算法是，将N项以任意顺序放入树中，保持结构特性。然后从最后一个叶子节点的父节点开始执行下滤操作，每一次下滤都会使得该子树有序。

示意图如下：

1. 以任意顺序构造的符合堆结构的二叉堆，并对最后一个叶节点的父节点执行下滤操作，使得该子树有序

2. 有序过后的子树

3. 对下标减一的节点进行下滤操作

4. 依次对下标递减的其他字树执行下滤操作，直到根节点

该建堆方法的代码实现（Java）为：

    /**
 * 二叉堆。
 * @param <AnyType> 需要排序的数组的类型，必须要实现Comparable接口，例如Integer等
 */
public class BinaryHeap <AnyType extends Comparable<? super AnyType>>{
    private AnyType[] arr; //二叉堆所在的数组
    private int currentSize; //currentSize 当前堆中的元素数目，注意，不是arr的大小
    /**
     * 二叉堆的下滤操作方法。
     * 可以使得以该节点为根节点的子树变得有序。deleteMin和buildheap操作均依赖于该方法。
     * @param hole 空洞位置在数组中的索引（需要排序的子树的根节点）
     */
    private  void percolateDown(int hole){
        int child;
        AnyType tmp = arr[hole];  //暂存空洞节点的值

        for(; hole*2 <= currentSize; hole = child){ //对子树遍历进行
            child = hole*2;
            if (child != currentSize && arr[child+1].compareTo(arr[child])<0) //找出两个子节点中的较小者
                child++;
            if (arr[child].compareTo(tmp)<0)  //子节点较小者与空洞值相比
                arr[hole] = arr[child];
            else
                break;
        }
        arr[hole] = tmp;
    }

    /**
     * 二叉堆的构造方法，接收包含节点的数组，并完成二叉堆的构造
     * @param items 一个无序的，包含所有节点，大小等于节点数的数组
     */
    public BinaryHeap(AnyType[] items) {
        currentSize = items.length;
        arr = (AnyType[]) new Comparable[(currentSize+2)*11/10];

        int i=1;
        for (AnyType item:items)
            arr[i++]=item;
        buildHeap();
    }

    /**
     * 构造堆的具体方法。
     */
    private void buildHeap() {
        for (int i = currentSize/2;i>0;i--){
            percolateDown(i);
        }
    }

    public AnyType[] getArr(){
        return arr;
    }
}

测试上面示意图中的堆：

    public class BHTest {
    public static void main(String[] args) {
        Integer[] items={1,5,7,9,4,6,2,11,8,3};
        BinaryHeap<Integer> heap=new BinaryHeap<Integer>(items);
        Comparable[] arr= heap.getArr();
        for (Comparable item:arr){
            System.out.println(item);
        }
    }
}

输出结果为：

null
1
3
2
8
4
6
7
11
9
5
null
null

优化建堆方法的时间复杂度分析

通过该算法建堆的时间复杂度为O(N)，证明过程会用到许多数学运算，详细的证明过程可以参考这篇博客：https://www.cnblogs.com/shytong/p/5364470.html