堆.md

大顶堆 和 小顶堆

先来了解下 堆 结构； 堆也被称为优先队列，二叉堆 ；

特点

• 堆总是一颗完全二叉树树， 使用数组作为其存储结构，因此也叫 二叉堆； 用链表存的就叫二叉树了
• 任一节点小于（或大于）其所有的孩子节点；

堆分小根堆和大根堆； 如果根节点大于所有孩子节点，这就是一颗大根堆，也就是根节点是堆上的最大值；如果节点小于所有的子节点，这就是一颗小跟堆，也即是根节点是堆上所有节点的最小值。

堆用数组来存储，因为是一颗完全二叉树，i节点的父节点索引就是(i-1)/2, 左右子节点小标是 2i+1，2i+2。

比如大根堆存储示例

10, 7, 6 , 3, 4, 1, 5 

应用场景

• 优先队列 如iOS中的 NSOperationQueue 就是维护一个优先队列
• 堆排序
• top-K 大(小) , top-k大 问题就是用 小根堆， 小根堆 固定为 k 个元素大小 ， 遍历 k-N (N为所有数据的个数)，插入小根堆并调整堆，以保证堆内的k个元素，总是当前最大的k个元素。

堆存储结构

堆的操作有：

• 建堆
• 插入：都是插入到数组最后，然后再调整满足堆次序
• 删除：删除总是发生在 A[0]处，也就是只删除根节点

这样难怪堆被称为 优先队列。 插入和删除分别在 数组尾部和头部，只是需要再次调整以满足堆次序。

堆调整

插入或删除元素以后， 如何进行堆调整， 已满足堆次序？

优先级队列的代码实现

public class MaxPQ
    <Key extends Comparable<Key>> {
    // 存储元素的数组
    private Key[] pq;
    // 当前 Priority Queue 中的元素个数
    private int N = 0;

    public MaxPQ(int cap) {
        // 索引 0 不用，所以多分配一个空间
        pq = (Key[]) new Comparable[cap + 1];
    }

    /* 返回当前队列中最大元素 */
    public Key max() {
        return pq[1];
    }

    /* 插入元素 e */
    public void insert(Key e) {...}

    /* 删除并返回当前队列中最大元素 */
    public Key delMax() {...}

    /* 上浮第 k 个元素，以维护最大堆性质 */
    private void swim(int k) {...}

    /* 下沉第 k 个元素，以维护最大堆性质 */
    private void sink(int k) {...}

    /* 交换数组的两个元素 */
    private void exch(int i, int j) {
        Key temp = pq[i];
        pq[i] = pq[j];
        pq[j] = temp;
    }

    /* pq[i] 是否比 pq[j] 小？ */
    private boolean less(int i, int j) {
        return pq[i].compareTo(pq[j]) < 0;
    }

    /* 还有 left, right, parent 三个方法 */
}