堆与优先队列

堆的定义

这里说的堆是指二叉堆,二叉堆是完全二叉树或者是近似完全二叉树。
二叉堆满足二个特性：

  • 父结点的键值总是大于或等于（小于或等于）任何一个子节点的键值。
  • 每个结点的左子树和右子树都是一个二叉堆（都是最大堆或最小堆）。

当父结点的键值总是大于或等于任何一个子节点的键值时为最大堆。当父结点的键值总是小于或等于任何一个子节点的键值时为最小堆

因为堆的本质是完全二叉树，因此

1
对于一个结点数为n的堆，其高度为lgn，证明过程可以设高度为h，则n>=2^h-1且n<2^(h+1)-1，即可推导出结果

因此插入或者移除一个元素的时间复杂度即为O(lgn)

优先队列

优先队列是一个无界队列，可以按照默认排序或者指定的comparator来排序，本质上仍然是一个堆，注意到这是非线程安全的。

堆的基本操作

往堆中添加元素其实就是要维护堆的属性，这里直接分析Java中优先队列的实现:

siftUpComparable是add的核心实现

1
2
3
4
5
6
7
8
9
10
11
12
private void siftUpComparable(int k, E x) {
    Comparable<? super E> key = (Comparable<? super E>) x;
    while (k > 0) {
        int parent = (k - 1) >>> 1;
        Object e = queue[parent];
        if (key.compareTo((E) e) >= 0)
            break;
        queue[k] = e;
        k = parent;
    }
    queue[k] = key;
}

其中

1
int parent = (k - 1) >>> 1;

这一行是找到节点的父节点，子节点下标除2取下界，然后比较当前元素与父节点的大小,若大于父节点，则直接停止循环，放入当前的k值中，k的初始值是堆的size，注意size是从1开始数的，而索引是从0开始的。此后K值一直保存parent的索引，只到key值放入了parent的位置中

siftDownComparable是remove和poll的核心实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
private void siftDownComparable(int k, E x) {
    Comparable<? super E> key = (Comparable<? super E>)x;
    int half = size >>> 1;        // loop while a non-leaf
    while (k < half) {
        int child = (k << 1) + 1; // assume left child is least
        Object c = queue[child];
        int right = child + 1;
        if (right < size &&
            ((Comparable<? super E>) c).compareTo((E) queue[right]) > 0)
            c = queue[child = right];
        if (key.compareTo((E) c) <= 0)
            break;
        queue[k] = c;
        k = child;
    }
    queue[k] = key;
}

remove和poll是移除head的结点，移除之后要重新生成一个根节点，思路是：从原根节点的子节点开始找，找到左右子节点中较小的开刀，比较其与Queue中最后一个元素key的大小，若key小，则直接作为根节点；若key大，则将这个子节点上位，置为根节点，再开始分析这个子节点的子节点，分析过程如前。