第四章：序列式容器 heap
heap概述
heap并不归属于STL容器组件，扮演priority queue的助手，binary max heap适合作为priority queue的底层机制，priority queue允许用户以任意次序将元素推入容器，但是取出是一定是优先权最高（数值最高）的元素先出来。binary heap是一种complete binary tree（完全二叉树），整棵binary tree除了最底层的叶子节点外是填满的，而最底层的叶子节点由左至右不得有空隙，如下图所示：
利用array来存储completebinary tree的所有节点，将array的#0元素保留，**那么当complete binary tree的某个节点位于array的i处时，其左子节点必位于array的2i处，右子节点必位于array的2i+1处，父节点必位于i/2处。**根据元素排列方式，heap分为max-heap和min-heap两种，前者每个节点的键值都大于或等于其子节点的值，后者每个节点的键值都小于或等于其子节点的值。max-heap中最大值在根节点，min-heap最小值在根节点。底层存储结构为vector或者array。STL 供应的是max-heap。heap的所有元素都必须遵循特别的排列规则，所以heap不提供遍历功能，也不提供迭代器。
heap算法
## push_heap算法
push_heap算法：将新加入的元素放在最下层的叶节点，即vector的end()处，还需满足max-heap条件，执行所谓的percolate up(上溯)过程，即不断比较新节点和其父节点，最终将其放到合适的位置。举例如下：
代码实现：
template<class RandomAccessIterator>
inline void push_heap(RandomAccessIterator first,RandomAccessIterator last){
//这个函数被调用时，新元素已经放在底部容器的最尾端
_push_heap_aux(first,last,distance_type(first),value_type(first));
}
template<class RandomAccessIterator,class Distance,class T>
inline void _push_heap_aux(RandomAccessIterator first,RandomAccessIterator last,Distance*,T*)
{_push_heap(first ,Distance((last-first)-1),Distance(0),T(*(last-1)));}
template<class RandomAccessIterator,class Distance,class T>
void _push_heap(RandomAccessIterator first,Distance holeIndex,Distance topIndex,T value)
{
Distence parent=(holeIndex-1)/2;//找出父节点
while(holeIndex>topIndex&&*(first+parent)<value){
//未到达顶端，父节点小于新值,使用<,所以STL heap是个max_heap。
*(first+holeIndex)=*(first +parent)//父值下移
holeIndex=parent;//调整位置，向上提升至父节点
parent=(holeIndex-1)/2;//找到新的父节点。
}//持续到顶端，或者满足heap的特性就停止了。
*(first+holeIndex)=value;//找到它应该处于的位置，插入操作结束。
｝
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
pop_heap
pop_heap算法：pop操作直接取根节点，为了满足max-heap条件，必须割舍最下层最右边的叶节点，并将其值重新安插至max-heap。为了满足max-heap次序特性，先执行percolate down(下溯）过程：将空间节点和其较大子节点“对调”，并持续下放，直至叶节点；然后将前述被割舍的元素值赋值给这个“已到达叶层的空洞节点”，再对它执行一次percolate up(上溯）过程，即可完成结构调整。
template <class RandomAccessIterator>//提供首尾两个迭代器，否则结果不可预知。
inline void pop_heap(RandomAccessIterator first, RandomAccessIterator last) {
__pop_heap_aux(first, last, value_type(first));
}
template <class RandomAccessIterator, class T>
inline void __pop_heap_aux(RandomAccessIterator first,
RandomAccessIterator last, T*) {
__pop_heap(first, last - 1, last - 1, T(*(last - 1)), distance_type(first));
// pop动作的結果为底层容器的第一個元素。因此，首先设定欲调整值为尾值，然后將首值調至
// 尾节点（所以以上將迭代器result设为last-1）。然后重整 [first, last-1)，
// 使之重新成一個合格的 heap。
}
template <class RandomAccessIterator, class T, class Distance>
inline void __pop_heap(RandomAccessIterator first, RandomAccessIterator last,
RandomAccessIterator result, T value, Distance*) {
*result = *first; // 設定尾值为首值，于是尾值即是結果，
// 可由调用底层容器之 pop_back() 取出尾值。
__adjust_heap(first, Distance(0), Distance(last - first), value);
// 以上欲重新調整 heap，洞号为 0，欲調整值为value。
}
template <class RandomAccessIterator, class Distance, class T>
void __adjust_heap(RandomAccessIterator first, Distance holeIndex,
Distance len, T value) {
Distance topIndex = holeIndex;
Distance secondChild = 2 * holeIndex + 2; // 洞节点之右子节点
while (secondChild < len) {
// 比较洞节点之左右兩个子值，然后以 secondChild 代表较大子节点。
if (*(first + secondChild) < *(first + (secondChild - 1)))
secondChild--;
// Percolate down：令较大大子值为洞值，再令洞号下移至较大子节点处。
*(first + holeIndex) = *(first + secondChild);
holeIndex = secondChild;
// 找出新洞节点的右子节点
secondChild = 2 * (secondChild + 1);
}
if (secondChild == len) { // 沒有右子节点，只有左子节点
// Percolate down：令左子值为洞值，再令洞号下移至左子节点处。
*(first + holeIndex) = *(first + (secondChild - 1));
holeIndex = secondChild - 1;
}
// 將欲调整值填入目前的洞号內。注意，此時肯定滿足次序特性。
// 依侯捷之见，下面直接改為 *(first + holeIndex) = value; 应该可以。
__push_heap(first, holeIndex, topIndex, value);
}
//此时的最大元素只是被放置在了底部容器的尾端，并未被取走，所以要取值，可以使用底部容器提供的back()操作函数，如果要移除，使用pop_back().
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
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
注意：pop_heap后，最大元素只是被置于底层容器的最尾部，尚未被取走。如果取值，可用back函数；如果移除，可用pop_back函数。
## sort_heap
既然每一pop_heap都将最大值放到vector的末尾，那么如果每次都缩小pop_heap的参数范围（从后向前缩减一个与元素），那么最终得到的vector将是一个递增序列。
// 以下這個 sort_heap() 不允許指定「大小比較標準」
template <class RandomAccessIterator>
void sort_heap(RandomAccessIterator first, RandomAccessIterator last) {
// 以下，每執行一次 pop_heap()，極值（在STL heap中為極大值）即被放在尾端。
// 扣除尾端再執行一次 pop_heap()，次極值又被放在新尾端。一直下去，最後即得
// 排序結果。
while (last - first > 1)
pop_heap(first, last--); // 每執行 pop_heap() 一次，操作範圍即退縮一格。
}
1
2
3
4
5
6
7
8
9
2
3
4
5
6
7
8
9
## make_heap
make_heap，将一段现有的数据转化成一个heap，代码如下：
// 將 [first,last) 排列為一個 heap。
template <class RandomAccessIterator>
inline void make_heap(RandomAccessIterator first, RandomAccessIterator last) {
__make_heap(first, last, value_type(first), distance_type(first));
}
// 以下這組 make_heap() 不允許指定「大小比較標準」。
template <class RandomAccessIterator, class T, class Distance>
void __make_heap(RandomAccessIterator first, RandomAccessIterator last, T*,
Distance*) {
if (last - first < 2) return; // 如果長度為 0 或 1，不必重新排列。
Distance len = last - first;
// 找出第一個需要重排的子樹頭部，以 parent 標示出。由於任何葉節點都不需執行
// perlocate down，所以有以下計算。parent 命名不佳，名為 holeIndex 更好。
Distance parent = (len - 2) / 2;//找出第一个有子节点的节点
while (true) {
// 重排以 parent 為首的子樹。len 是為了讓 __adjust_heap() 判斷操作範圍
__adjust_heap(first, parent, len, T(*(first + parent)));//下溯程序
if (parent == 0) return; // 排序到根節點，程序就結束。
parent--; // （重排之子樹的）頭部向前一個節點，迭代过程，排序完一个就接着排序前一个。
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
heap测试实例
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
{
// test heap (以vector完成)
int ia[9] = {0, 1, 2, 3, 4, 8, 9, 3, 5};
vector<int> ivec(ia, ia + 9);
make_heap(ivec.begin(), ivec.end());
for (int i = 0; i < ivec.size(); ++i) {
cout << ivec[i] << " "; // 9 5 8 3 4 0 2 3 1
}
cout << endl;
ivec.push_back(7);
push_heap(ivec.begin(), ivec.end());
for (int i = 0; i < ivec.size(); ++i) {
cout << ivec[i] << " "; // 9 5 8 3 4 0 2 3 1 4
}
cout << endl;
pop_heap(ivec.begin(), ivec.end());
cout << ivec.back() << endl; // 9
ivec.pop_back();
for (int i = 0; i < ivec.size(); ++i) {
cout << ivec[i] << " "; // 8 7 4 3 5 0 2 3 1
}
cout << endl;
sort_heap(ivec.begin(), ivec.end());
for (int i = 0; i < ivec.size(); ++i) {
cout << ivec[i] << " "; // 0 1 2 3 3 4 5 7 8
}
cout << endl;
}
{
// test heap (以array完成)
int ia[9] = {0, 1, 2, 3, 4, 8, 9, 3, 5};
make_heap(ia, ia+9);
// array无法动态改变大小，因此不可以对满载的 array做 push_heap()动作。
//因为那得先在 array尾端增加㆒个元素。
sort_heap(ia, ia+9);
for (int i = 0; i < 9; ++i) {
cout << ia[i] << " "; // 0 1 2 3 3 4 5 8 9
}
cout << endl;
make_heap(ia, ia+9);
pop_heap(ia, ia+9);
cout << ia[8] << endl; // 9
}
{
// test heap (底层以 array完成)
int ia[6] = {4,1,7,6,2,5};
make_heap(ia, ia+6);
for(int i=0; i<6; ++i)
cout << ia[i] << ' '; // 7 6 5 1 2 4
cout << endl;
}
}
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
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