队列的特点是FIFO，遵循一个先来后到，但是如果有的任务本身执行时间很短但由于排队时间太长导致执行过慢就不是很合逻辑，因此就有了优先队列（priority queue）这样的数据结构，优先队列同样有入栈和出栈，特殊的地方在于出栈是找到其中min然后出栈，定义实现了优先队列的数据结构叫堆（heap）

堆的性质

结构性

堆又叫做完全二叉树，它的特点是所有节点都被填满，除了底层之后，并且底层的元素是从左向右填入（左有右没有），这里需要区分满二叉树：所有节点都填满。

完全二叉树有个规律，它可以直接用数组来表示出来

1
2
3
4
5
6
7
         A
      /    \
     B      C
   /   \   / \
  D     E F   G
 / \   /
H   I j
1
2
A B C D E F G H I J
1 2 3 4 5 6 7 8 9 10

对于i上的元素x，x的父节点是array[i/2]，左儿子是array[2i]，右儿子是array[2i+1]。
这样的好处在于一个完全二叉树可以用一个数组来表示，另外需要一个表示数组大小的整型变量。

堆序性

因为每次出栈都是弹出min元素，因此需要把min元素放在root上是最简单的。这就需要插入或者删除的时候需要调整堆来保证堆序性（也需要保证结构性）。
堆序性可以这样表述: 对于i上的元素x来说，x永远大于等于x的父节点（array[i/2]）

1
2
3
4
5
6
     13                      13
   /   \                    /  \
  25   36                  7   16
 /  \                     / \
66  77                   23  32
满足堆序性                  由于7<13，因此不满足堆序性

要保证这样的堆序性就是为了root节点是min节点，最简单最快的找到min节点。

插入

假设有这样的一个堆，向该堆中插入14。

1
2
3
4
5
6
7
             13
       /            \
      21             16
    /     \         /   \
  24      31       19    68
 /  \     / \
65   26  32

堆有个性质可以用数组来表示

1
2
   13 21 16 24 31 19 68 65 26 32   14
0  1  2  3  4  5  6  7  8  9  10   11

如果只是把14插入最后就破坏了堆序性：14 > array[11/2] (array[5] = 31)，因此我们将14和31交换位置，发现14依然小于他的父节点（array[5/2] = 21），继续和21交换位置，由于14大于他的父节点13，所以插入到此结束。

1
2
3
4
5
6
7
public insert (int x) {
    int hole = currentSize++;
    for (array[0] = x ; x.compareTo(array[hole/2] <0) ; hole /= 2) {
        array[hole] = array[hole/2];
    }
    array[hole] = x;
}

由于是在底层然后一层层往上找空位的，因此这个操作叫上滤。

删除最小元

由于root节点就是最小元，因此要寻找它不怎么难，但是将他删除之后的空位需要怎么填补是个问题。

1
2
3
4
5
6
7
             13
       /            \
      14             16
    /     \         /   \
  24      21       19    68
 /  \     / \
65   26  32  31

因此只能用min节点的子节点中偏小的那个来填充这个空。如上述的堆中，13没了之后应该用14来填补，然后14又空出来了，继续用21来填补，而21又空出来了，因此用31来填补，所以删除了13之后变成了这样

1
2
3
4
5
6
7
             14
       /            \
      21             16
    /     \         /   \
  24      31       19    68
 /  \     /
65   26  32
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public T deleteMin() {
    T min = findMin();
    array[1] = array[currentSize--];
    percolateDown(1);
    return min;
}
public void percolateDown(int hole) {
    int child;
    T tmp = array[hole];
    for (;hole * 2 <= currentSize;chile = hole) {
        child = hole * 2;
        if (child != currentSize && array[chile].compareTo(array[child + 1]) < 0) {
            child++;
        }
        if (array[hole] < array[childe]) {
            break;
        } else {
            array[hole] = array[child];
        }
    }
    array[hole] = tmp;
}

具体实现的思路是将最后一个值先放入min节点中，然后层层向下和子节点比较，直到找到合适的位置，这种操作叫做下滤。