一.heap
在STL中，priority_queue（优先权队列）的底层机制是最大堆，因此有必要先来了解一下heap。heap采用完全二叉树的结构，当然不是真正的binary tree，因为对于完全二叉树，我们通常用一个数组来表示。
以下几个算法都是STL的泛型算法，包含在头文件algorithm里，priority_queue的push()，pop()都有直接调用它们。
1.push_heap算法
首先，将新元素插入到底层vector的end()处。为了满足最大堆原理（每个结点的值必须大于或等于其子结点的值），于是将新结点与其父亲结点比较，如果其值大于父亲结点，就交换父子结点，直到不需要交换或者它已经到达根结点为止。
2.pop_heap算法
因为作为最大堆，根结点即为最大值。交换vector首尾（first和last）元素，并重新调整[first，last-1)部分，也就是将“新根结点”跟其较大子结点交换，并持续下放，知道叶子结点为止。注意，pop_heap之后，最大元素只是被放在底部容器的最尾端，并没有被取走。若要取走，可用vector的pop_back()函数。
3.sort_heap算法
持续对整个heap做pop_heap操作，每次将操作范围从后向前缩减一个元素，于是我们得到一个递增序列。显然，排序后的heap不是一个合法的heap了。
4.make_heap算法
这个算法用来将数组转化成一个heap。
二.priority_queue
顾名思义，priority_queue是一个拥有权值观念的queue。由于这是一个queue，所以只允许在底端加入元素，并从顶端取出元素，除此之外没有其他存取元素的途径，所以priority_queue没有迭代器，不提供遍历功能。
注意，priority_queue缺省情况下是以vector为底部容器，并不是deque，而queue是以deque为底部容器。
三.堆排序
了解以上内容后，最重要的是我们可以自己写出一个堆排序算法，而不是简单的应用这些泛型算法。当然了，限于本人水平，肯定与源码有天壤之别，只是一个简单的堆排序算法而已。
|
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
|
void
AdjustDown(vector<int> &A,int
index,int
rindex)
{ int
len=A.size();
int
child=2*index+1; //左孩子下标
int
temp=A[index];
while(child<=rindex)
{
if(child<rindex&&A[child]<A[child+1]) //若右孩子大于左孩子
child++; //child指向右孩子
if(temp>=A[child]) break; //父结点大于孩子结点，无需调整
A[(child-1)/2]=A[child]; //否则父结点放较大孩子
child=2*child+1; //child指向“空”结点左孩子
}
A[(child-1)/2]=temp; //空结点放需要调整（index）的值
}void
HeapSort(vector<int> &A)
{ int
i;
int
len=A.size();
for(i=(len-2)/2;i>=0;i--) //make_heap
AdjustDown(A,i,len-1);
for(i=len-1;i>0;i--)
{
swap(A[0],A[i]);
AdjustDown(A,0,i-1);
}
} |