###二叉堆
二叉堆是一个数组,它可以被看成一个近似的完全二叉树。如图一。树上的每个节点都对应数组中的一个元素。除了最底层外,该树是完全充满的,而且是从左向右填充。

kmp1

二叉堆可以分为两种形式:最大堆和最小堆。在最大堆中,每一个父节点的值都要大于子节点的值;在最小堆中,每一个父节点的值都要小于子节点的值。

堆的主要操作是实现插入元素和删除最大元素(最大堆)。

####由下至上的堆有序化(上浮)
(最大堆)如果堆的有序状态因为某个节点变得比它的父节点更大而被打破,那么我们就需要通过交换它和它的父节点来修复堆。如果交换后它仍比父节点大,那继续交换直至遇到一个比它大的父节点。

这种方法主要用在建堆的时候,即插入元素的时候。

1
2
3
4
5
6
private void swim(int k) {
while (k > 1 && less(k/2, k)) {
exch(k/2, k);
k = k/2;
}
}

####有上至下的堆的有序化(下沉)
(最大堆)如果堆的有序状态因为某个结点变得比它的两个子结点更小而被打破,那么我们就要不断交换它和它的两个子结点的较大者来修复堆。直至它比它的两个子结点都大。

这种方法主要用在删除元素后的恢复堆上。

1
2
3
4
5
6
7
8
9
10
11
12
private void sink(int k) {
while (2*k <= N) {
int j = 2*k;
//找到子结点中较大的结点
if (j < N && less(j, j+1))
j++;
//如果父结点比子结点大,结束
if (!less(k, j))
break;
exch(k, j);
}
}

####二叉堆的实现:
二叉堆有可以做优先级队列,如下是实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
public class MaxPQ<Key extends Comparable<Key>> {
//在这里,我们使用长度为N+1的数组来存储N个数,位置从1开始
private Key[] pq;
private int N = 0;
public MaxPQ(int maxN) {
pq = (Key[]) new Comparable[maxN+1];
}
public boolean isEmpty() {
return N == 0;
}
public int size() {
return N;
}
public void insert(Key v) {
pq[++N] = v;
swim(N);
}
public Key delMax() {
Key max = pq[1];
exch(1, N--);
pq[N+1] = null;
sink(1);
return max;
}
private boolean less(int i, int j) {
return ((Comparable<Key>) pq[i]).compareTo(pq[j]) < 0;
}
private void exch(int i, int j) {
Key swap = pq[i];
pq[i] = pq[j];
pq[j] = swap;
}
}

###堆排序
由于最大堆在上面已经介绍,所以堆排序的思想其实很简单。我们可以根据需要排序的数组构造一个最大堆,然后我们依次将堆的第一个数即最大的数换到堆的最后,然后将堆的大小减一即可。

1
2
3
4
5
6
7
8
9
10
11
12
public static void heapSort(Comparable[] a) {
int N = a.length;
//需要注意的是,在这里我们从N/2开始修复最大堆,因为大于N/2的都是叶子结点
//不需要修复
for (int k = N/2; k >= 1; k--)
sink(a, k, N);
while (N > 1) {
exch(a, 1, N--);
sink(a, 1, N);
}
}