一、堆的概念

如果有一个关键码的集合K = {k0，k1， k2，…，kn-1}，把它的所有元素按完全二叉树的顺序存储方式（层序遍历）存储在一个一维数组中，并满足：Ki <= K2i+1 且 Ki<= K2i+2 (Ki >= K2i+1 且 Ki >= K2i+2) i = 0，1，2…，则称为小堆(或大堆)。将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。
堆的性质：

堆中某个节点的值总是不大于或不小于其父节点的值；
堆总是一棵完全二叉树。

二、堆的存储方式

从堆的概念可知，堆是一棵完全二叉树，因此可以层序的规则采用顺序的方式来高效存储。

注意：对于非完全二叉树，则不适合使用顺序方式进行存储，因为为了能够还原二叉树，空间中必须要存储空节点，就会导致空间利用率比较低。
将元素存储到数组中后，可以根据二叉树章节的性质5对树进行还原。假设i为节点在数组中的下标，则有：

如果i为0，则i表示的节点为根节点，否则i节点的双亲节点为 (i – 1)/2；
如果2 * i + 1 小于节点个数，则节点i的左孩子下标为2 * i + 1，否则没有左孩子；
如果2 * i + 2 小于节点个数，则节点i的右孩子下标为2 * i + 2，否则没有右孩子。

三、堆的创建

3.1 堆向下调整

对于集合{ 27,15,19,18,28,34,65,49,25,37 }中的数据，如果将其创建成堆呢？

仔细观察上图后发现：根节点的左右子树已经完全满足堆的性质，因此只需将根节点向下调整好即可。
向下过程(以小堆为例)：

让parent标记需要调整的节点，child标记parent的左孩子(注意：parent如果有孩子一定先是有左孩子)；
如果parent的左孩子存在，即:child < size，进行以下操作，直到parent的左孩子不存在：
○ parent右孩子是否存在，存在找到左右孩子中最小的孩子，让child进行标记；
○ 将parent与较小的孩子child比较：
如果： parent小于较小的孩子child，调整结束；否则： 交换parent与较小的孩子child，交换完成之后，parent中大的元素向下移动，可能导致子树不满足对的性质，因此需要继续向下调整，即parent = child；child = parent*2+1; 然后继续2。

注意：在调整以parent为根的二叉树时，必须要满足parent的左子树和右子树已经是堆了才可以向下调整。
时间复杂度分析：
最坏的情况即图示的情况，从根一路比较到叶子，比较的次数为完全二叉树的高度，即时间复杂度为O(log₂N)。

3.2 堆的创建

那对于普通的序列{ 1,5,3,8,7,6 }，即根节点的左右子树不满足堆的特性，又该如何调整呢？

3.3 参考代码（大根堆）

public class MyHeap {
    public int[] elem;
    public int usedSize;
    public static final int DEFAULT_SIZE = 10;

    public MyHeap(){
        elem = new int[DEFAULT_SIZE];
    }

    public void initElem(int[] array){
        for (int i = 0; i < array.length; i++) {
            elem[i] = array[i];
            usedSize++;
        }
    }

    public void createHeap(){
        // 找倒数第一个非叶子节点，从该节点位置开始往前一直到根节点，遇到一个节点，应用向下调整
        for (int parent = (usedSize-1-1)/2; parent >= 0 ; parent--) {
            // 统一的调整方案
            shiftDown(parent,usedSize);
        }
    }

    /**
     *
     * @param parent 每个父亲节点
     * @param len 每颗子树调整的结束位置必须＜len
     */
    private void shiftDown(int parent,int len){
        int child = 2*parent+1;
        // 必须保证有左孩子
        while(child < len){
            // 有右孩子时才判断(下行语句的顺序不能变！)
            if(child+1 < len && elem[child+1] > elem[child]){
                child++;
            }
            // 到这里，child下标一定是左右孩子最大值的下标
            if(elem[child] > elem[parent]){
                int tmp = elem[child];
                elem[child] = elem[parent];
                elem[parent] = tmp;
                parent = child;
                child = 2*parent+1;
            }else{
                // 因为是从下面调上来的，所以若符合大根堆下面一定也符合,可以直接break
                break;
            }
        }
    }
}

3.4 建堆的时间复杂度

因为堆是完全二叉树，而满二叉树也是完全二叉树，此处为了简化使用满二叉树来证明（时间复杂度本来看的就是近似值，多几个节点不影响最终结果）：

因此：建堆的时间复杂度为O(N)。
（若为向上调整建堆，时间复杂度为O(Nlog₂N)）
（优先级队列插入数据时，相当于向上调整）

四、堆的插入与删除

4.1 堆的插入

堆的插入总共需要两个步骤：

先将元素放入到底层空间中(注意：空间不够时需要扩容)
将最后新插入的节点向上调整，直到满足堆的性质

代码实现：

    public void offer(int val){
        if(isFull()){
            // 扩容
            elem = Arrays.copyOf(elem,2*elem.length);
        }
        this.elem[usedSize] = val;
        usedSize++;
        // 再次调整为大根堆
        shiftUp(usedSize-1);

    }

    private void shiftUp(int child){
        int parent = (child-1)/2;
        while(parent >= 0){       // 这里一定是parent>=0 或者 是child>而不是parent> (顺着逻辑想一下)
            if(elem[child] > elem[parent]){
                int tmp = elem[child];
                elem[child] = elem[parent];
                elem[parent] = tmp;
                child = parent;
                parent = (child-1)/2;
            }else{
                break;
            }
        }
    }

    public boolean isFull(){
        return usedSize == elem.length;
    }

4.2 堆的删除

注意：堆的删除一定删除的是堆顶元素。 具体如下：

将堆顶元素对堆中最后一个元素交换
将堆中有效数据个数减少一个
对堆顶元素进行向下调整

代码实现：

    public int pop(){
        if(isEmpty()){
            return -1;
        }
        int tmp = elem[0];
        elem[0] = elem[usedSize-1];
        elem[usedSize-1] = tmp;
        usedSize--;
        // 保证依然是大根堆
        shiftDown(0,usedSize);
        return tmp;
    }

    public boolean isEmpty(){
        return usedSize == 0;
    }

五、堆的应用

5.1 PriorityQueue的实现

用堆作为底层结构封装优先级队列：优先级队列PriorityQueue 博客链接

5.2 堆排序

堆排序即利用堆的思想来进行排序，总共分为两个步骤：

建堆
升序：建大堆；降序：建小堆。
例如升序：
小根堆是不可以实现的，原因：
每次弹出的是最小的，没问题，但是，弹出去之后，放到哪里？
此时你的空间复杂度就是最大了：O(N) ！！！
利用堆删除思想来进行排序
从后往前逐渐有序！！！
建堆和堆删除中都用到了向下调整，因此掌握了向下调整，就可以完成堆排序。

升序代码实现：

    public void heapSort(){
        // 1.先建立大根堆
        createHeap();
        // 2.然后排序
        int end = usedSize - 1;
        while(end > 0){
            int tmp = elem[0];
            elem[0] = elem[end];
            elem[end] = tmp;
            shiftDown(0,end);
            end--;
        }
    }

    public void createHeap(){
        // 找倒数第一个非叶子节点，从该节点位置开始往前一直到根节点，遇到一个节点，应用向下调整
        for (int parent = (usedSize-1-1)/2; parent >= 0 ; parent--) {
            // 统一的调整方案
            shiftDown(parent,usedSize);
        }
    }

    private void shiftDown(int parent,int len){
        int child = 2*parent+1;
        // 必须保证有左孩子
        while(child < len){
            // 有右孩子时才判断(下行语句的顺序不能变！)
            if(child+1 < len && elem[child+1] > elem[child]){
                child++;
            }
            // 到这里，child下标一定是左右孩子最大值的下标
            if(elem[child] > elem[parent]){
                int tmp = elem[child];
                elem[child] = elem[parent];
                elem[parent] = tmp;
                parent = child;
                child = 2*parent+1;
            }else{
                // 因为是从下面调上来的，所以若符合大根堆下面一定也符合,可以直接break
                break;
            }
        }
    }