【编程珠玑】第十四章：堆（排序，优先级队列）
一，堆
1）堆：任何结点的值都小于或等于其孩子的值的完全二叉树为小根堆
任何结点的值都大于或等于其孩子的值的完全二叉树为大根堆
为了方便使用完全二叉树的性质，数组从下标1开始。
这样：leftChild = 2*i ;
rightChild = 2*i + 1 ;
parent = i/2 ;
null i < 1 or i > n
2）堆算法分析
堆排序的最坏时间复杂度为O(nlogn)。堆序的平均性能较接近于最坏性能。
由于建初始堆所需的比较次数较多，所以堆排序不适宜于记录数较少的文件。
堆排序是就地排序，辅助空间为O(1）
堆排序是不稳顶的
3）堆实现
【特别注意】堆不一定是完全二叉树但是一般采用完全二叉树,主要是利于存储和运算。堆排序作用在数组上
初始建立堆：
给一个数组，将数组看做完全二叉树。
从最后一个非叶结点（length/2，下标从1开始），直到第一个结点a[1]，向上调整建立堆。
排序和堆调整
将第一个值a[1] 跟最后一个值交换，然后对 a[1] 调整堆（此时数组长度调整为length-1）
【注意】这里初始建堆，只考虑已经有n个元素，向下调整建堆就可以搞定。
但是对于insert（t）怎么办？ 采用向上调整堆的策略。详细见下文优先队列。
4）源码
[html]
#include"stdio.h"
inline void swap(int &a,int &b)
{
int temp=a;
a=b;
b=temp;
}
void HeapAdjust(int array[],int i,int nLength)//自顶向下调整堆
{
int nChild;
int nTemp;//赋值为待调整的 节点
for(nTemp=array[i];2*i<nLength;i=nChild)//2*i<nLength说明还有左孩子
{
nChild=2*i;//左孩子
/*一共两个子节点的话得到 较大的一个*/
if(nChild<nLength-1&&array[nChild+1]>array[nChild])//nChild<nLength-1 判断到头没有
++nChild;
/*如果较大子节点大于父节点 将子节点 调整到父节点*/
if(nTemp<array[nChild])
array[i]=array[nChild];
else
break;//这个地方不加 会出错 第一个会输出第二个
array[nChild]=nTemp;//子节点 等于父节点 （不执行break）
}
}
void HeapSort(int a[],int length)
{
/*初建堆 */
for(int i=length/2;i>0;--i)//从最后一个 非叶子节点调整 （这里的 i是下标）
HeapAdjust(a,i,length);
for(int i=length;i>1;--i)
{
swap(a[1],a[i]); /*第一个最大元素跟最后一个交换*/
HeapAdjust(a,1,i);//调整堆 (注意 length=i 由于堆是逐渐变小的)
}
}
int main()
{
int a[10]={0,1,2,5,3,8,4,7,6};
HeapSort(a,8);
for(int i=1;i<9;i++)
printf("%d\n",a[i]);
return 0;
}
二，优先队列
1）优先队列是0个或多个元素的集合,每个元素都有一个优先权或值,对优先队列执行的操作有1) 查找; 2) 插入一个新元素; 3) 删除.
在最小优先队列(min priorityq u e u e)中,查找操作用来搜索优先权最小的元素,删除操作用来删除该元素;
对于最大优先队列(max priority queue),查找操作用来搜索优先权最大的元素,删除操作用来删除该元素.
优先权队列中的元素可以有相同的优先权,查找与删除操作可根据任意优先权进行.
2）优先队列实现
初始化一个数组，向空数组依次插入元素，每插入一个元素向上调整一次堆。
删除元素，将第一个元素跟最后一个元素交换，并向下调整堆
3）代码实现
[html]
#include <iostream>
using namespace std;
template<class T>
class priqueue {
private:
int n, maxsize;
