一、堆的概念
1、堆是一个完全二叉树，它的所有元素按照完全二叉树的顺序存储方式存储在一个一维数组中。
2、堆中某个节点的值总是不大于或不小于其父节点的值；堆总是一棵完全二叉树。
3、堆分为两种：大顶堆、小顶堆
- 大顶堆：每一个父结点的值均大于等于其对应的子结点的值，而父结点的值就是最大的
- 小顶堆：每一个父结点的值均小于等于其对应的子结点的值，而父结点的值就是最小的
4、堆排序最后一个非叶子节点（父节点）的序号是n/2-1，n为数组的长度（具体分析见第四点）。
二、堆的实现
有两种方法，一种是自己写堆进行排序，一种是直接对数组建堆。
1、手动实现堆
假设我们排升序，且堆为小顶堆。
首先，把数组的每个元素（HeapPush）插入到堆中；
其次，小顶堆的堆顶是最小的数字，依次遍历堆顶的元素，将堆顶元素赋值到数组里，从下标0开始，赋值后删除堆顶元素，++数组下标；
此时堆就会重新调整，最终堆顶依旧是最小的，再重复上述赋值堆顶到数组的操作，直到堆为空。
具体实现可以参考堆的实现和堆排序和Topk问题。
2、数组建堆
堆的调整无非就两种，一种是向下调整，一种是向上调整。
向下调整：让调整的结点与其孩子节点进行比较
向上调整：让调整的结点与其父亲结点进行比较
简单区分就是，向下调整条件是孩子节点值比父节点小；而向上调整条件是父节点值比孩子节点小。
以数组[9, 2, 7, 5, 6, 4, 3, 8, 9]为例
![image]()
2-1、向下调整
思路：选出左右孩子中小的那一个，跟父节点比较，如果父节点大，则父节点和子节点交换。
记住一点，child = 2*parent + 1，这里child是左子树
首先取左右child更小的那个跟parent节点比较，如果parent节点更大，就把child的值和parent的值互换，同时parent下移到child的位置，用公式child = 2*parent + 1更新child位置；然后换行，比较下一层的parent和child。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
void adjust_down(int array[], int i, int n) {
int parent = i;
int child = 2 * i + 1;
while (child < n) {
if (child + 1 < n && array[child] > array[child + 1]) {
child++;
}
if (array[child] < array[parent]) {
swap(array, parent, child);
parent = child;
} else {
break;
}
child = child * 2 + 1;
}
}
|
2-2、建小顶堆
在向下调整中，要保证左子树和右子树均是堆，否则不能；按照这个思路，那采用向下调整建堆时，应该从下往上走，保证左右子树都是堆。
从最后一个非叶子节点开始，即n/2-1，调用一次向下调整；再找到前一个节点，调用一次向下调整，循环往复，直到对父节点向下调整（此时父节点的左右子树已是堆），堆就实现了。
举例：
1、对于数组[9, 2, 7, 5, 6, 4, 3, 8, 9]，n/2-1就是第3个节点，也就是5，取左右子树小的那个，即8，5小于8，不换，跳出循环；
2、下一个节点是7，取左右子树小的那个，即3，7大于3，互换，parent到3的位置，没有子树了，跳出调整。
1
2
3
4
5
6
7
|
void BuildMinHeap(int array[], int size) {
for (int i = size / 2 - 1; i >= 0; i--) {
adjust_down(array, i, size);
}
}
|
2-3、向上调整
思路：选出左右孩子中大的那一个，跟父节点比较，如果父节点小，则父节点和子节点交换。
记住一点，child = 2*parent + 1，这里child是左子树
首先取左右child更大的那个跟parent节点比较，如果parent节点更小，就把child的值和parent的值互换，同时parent下移到child的位置，用公式child = 2*parent + 1更新child位置；然后换行，比较下一层的parent和child。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
void adjust_up(int array[], int i, int n) {
int parent = i;
int child = 2 * i + 1;
while (child < n) {
if (child + 1 < n && array[child] < array[child + 1]) {
child++;
}
if (array[parent] < array[child]) {
swap(array, parent, child);
parent = child;
} else {
break;
}
child = child * 2 + 1;
}
}
|
2-4、建大顶堆
跟建小顶堆一样，在向上调整中，要保证左子树和右子树均是堆，否则不能；按照这个思路，那采用向上调整建堆时，应该从下往上走，保证左右子树都是堆。
从最后一个非叶子节点开始，即n/2-1，调用一次向下调整；再找到前一个节点，调用一次向上调整，循环往复，直到对父节点向上调整（此时父节点的左右子树已是堆），堆就实现了。
1
2
3
4
5
6
7
|
void BuildMaxHeap(int array[], int size) {
for (int i = size / 2 - 1; i >= 0; i--) {
adjust_up(array, i, size);
}
}
|
三、堆排序
有了上面的建堆，就可以直接进行堆排序了。
对于降序，我们可以先创建小顶堆，此时顶点是最小值。从后面开始遍历数组，每次遍历就交换顶点和第i个数据，这样就可以把顶点的最小值存到尾部；然后在剩余的数字中再进行向下调整，重新建立小顶堆；再进行上面的互换操作。
对于升序，也是类似的，先创建大顶堆，此时顶点是最大值。从后面开始遍历数组，每次遍历就交换顶点和第i个数据，这样就可以把顶点的最大值存到尾部；然后在剩余的数字中再进行向上调整，重新建立大顶堆；再进行上面的互换操作。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
void MaxHeapSort(int array[], int size) {
BuildMinHeap(array, size);
display(array, size);
for (int i = size - 1; i > 0; i--) {
swap(array, 0, i);
adjust_down(array, 0, i);
}
}
void MinHeapSort(int array[], int size) {
BuildMaxHeap(array, size);
display(array, size);
for (int i = size - 1; i > 0; i--) {
swap(array, 0, i);
adjust_up(array, 0, i);
}
}
|
四、堆排序最后一个非叶子节点的序号
堆排序是基于完全二叉树实现的，在将一个数组调整成一个堆的时候，关键之一的是确定最后一个非叶子节点的序号，这个序号为n/2-1，n为数组的长度。但是为什么呢？
可以分两种情况考虑：
1、堆的最后一个非叶子节点只有左孩子
2、堆的最后一个非叶子节点有左右两个孩子
完全二叉树的性质之一是：如果节点序号为 i，则它的左孩子序号为2i+1，右孩子序号为 2i+2。
对于情况1，左孩子(最后一个元素)的序号为 n-1，则 n-1=2i+1，推出 i=n/2-1；
对于情况2，左孩子(倒数第二个元素)的序号为 n-2，则 n-2=2i+1，推出i=(n-1)/2-1；右孩子(最后一个元素)的序号为n-1，则n-1=2i+2，推出（这里跟左孩子推出的一样）i=(n-1)/2-1。
很显然，当完全二叉树最后一个节点是其父节点的左孩子时，树的节点数（数组元素数）为偶数；当完全二叉树最后一个节点是其父节点的右孩子时（满二叉树），树的节点数（数组元素数）为奇数。
根据一般编程语言的特性，整数除不尽时向下取整，则若n为奇数时(n-1)/2-1=n/2-1。
因此对于情况2，最后一个非叶子节点的序号也是n/2-1。
五、完整代码
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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
| void display(int array[], int size) {
for (int i = 0; i < size; i++) {
printf("%d ", array[i]);
}
printf("\n");
}
void swap(int array[], int x, int y) {
int temp = array[x];
array[x] = array[y];
array[y] = temp;
}
void adjust_down(int array[], int i, int n) {
int parent = i;
int child = 2 * i + 1;
while (child < n) {
if (child + 1 < n && array[child] > array[child + 1]) {
child++;
}
if (array[parent] > array[child]) {
swap(array, parent, child);
parent = child;
} else {
break;
}
child = child * 2 + 1;
}
}
void adjust_up(int array[], int i, int n) {
int parent = i;
int child = 2 * i + 1;
while (child < n) {
if (child + 1 < n && array[child] < array[child + 1]) {
child++;
}
if (array[parent] < array[child]) {
swap(array, parent, child);
parent = child;
} else {
break;
}
child = child * 2 + 1;
}
}
void BuildMinHeap(int array[], int size) {
for (int i = size / 2 - 1; i >= 0; i--) {
adjust_down(array, i, size);
}
}
void BuildMaxHeap(int array[], int size) {
for (int i = size / 2 - 1; i >= 0; i--) {
adjust_up(array, i, size);
}
}
void MaxHeapSort(int array[], int size) {
BuildMinHeap(array, size);
display(array, size);
for (int i = size - 1; i > 0; i--) {
swap(array, 0, i);
adjust_down(array, 0, i);
}
}
void MinHeapSort(int array[], int size) {
BuildMaxHeap(array, size);
display(array, size);
for (int i = size - 1; i > 0; i--) {
swap(array, 0, i);
adjust_up(array, 0, i);
}
}
int main() {
int array[] = {9, 2, 7, 5, 6, 4, 3, 8, 9};
int size = sizeof(array) / sizeof(int);
display(array, size);
MinHeapSort(array, size);
display(array, size);
return 0;
}
|
