一、简介
堆数据结构的性质：堆：任何结点的值都小于或等于其孩子的值的完全二叉树为小根堆，任何结点的值都大于或等于其孩子的值的完全二叉树为大根堆。为了方便使用完全二叉树的性质，假定数组从下标1开始。这样：
leftChild = 2*i; rightChild = 2*i + 1; parent = i/2;
堆数据结构算法分析：
堆排序的最坏时间复杂度为O(nlogn)。堆序的平均性能较接近于最坏性能。由于建初始堆所需的比较次数较多，所以堆排序不适宜于记录数较少的文件。堆排序是就地排序，辅助空间为O(1)。堆排序是不稳定的。
堆数据结构实现如下所示：
#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;
}
利用堆数据结构可实现优先级队列，优先队列是0个或多个元素的集合,每个元素都有一个优先权或值,对优先队列执行的操作有查找、插入一个新元素和删除。在最小优先队列(min priority queue)中，查找操作用来搜索优先权最小的元素，删除操作用来删除该元素；对于最大优先队列(max priority queue)，查找操作用来搜索优先权最大的元素，删除操作用来删除该元素。优先权队列中的元素可以有相同的优先权，查找与删除操作可根据任意优先权进行。
优先级队列代码实现如下所示：
#include <iostream>
using namespace std;
template<class T>
class priqueue {
private:
int n, maxsize;
T *x;
void swap(int &i, int &j)//根据坐标交换数组元素的值
{ T t = i; i = j; j = t; }
public:
priqueue(int m)//初始化数组
{ maxsize = m;
x = new T[maxsize+1];
n = 0;
}
void insert(T t)
{ int i, p;
x[++n] = t; //插入的元素放到最后
for (i = n; i > 1 && x[p=i/2] > x[i]; i = p)
swap(x[p], x[i]);
}
T extractmin()//向下调整堆
{
int i, c;
T t = x[1];
x[1] = x[n--];
for (i = 1; (c=2*i) <= n; i = c) {
if (c+1<=n && x[c+1]<x[c])
c++;
if (x[i] <= x[c])
break;
swap(x[c], x[i]);
}
return t;
}
void print(int n)
{
for (int i = 1; i < n; i++) //输出堆
cout << x[i] << " ";
}
};
template<class T>
void pqsort(T v[], int n)//先初始化一个数组，然后插入建立一个堆
{ priqueue<T> pq(n);
int i;
for (i = 0; i < n; i++)
pq.insert(v[i]);
cout<<"输出排序后的堆：";
pq.print(n);
}
int main()
{ const int n = 10;
int i, v[n];
/*以下是通过向上调整堆 建立一个10个元素的堆*/
for (i = 0; i < n; i++)
v[i] = n-i;
pqsort(v, n);
cout<<"\n执行插入和删除操作(输入0代表删除最小值，输入其他代表插入)"<<endl;
priqueue<int> pq(100);
int count=0;
while (cin >> i)
if (i == 0)
{
if(count)
cout <<"删除的最小元素为："<<pq.extractmin() << "\n";
else
cout<<"请先插入元素"<<endl;
}
else
{
pq.insert(i);
count++;
}
return 0;
}
二、原理
（1）高效性。堆中所有结点和根结点之间相差的层数在logn之内。因此其执行效率很高，堆排序通过在同一数组中包含两种抽象结构（堆和元素序列）来避免使用额外空间。
（2）正确性，即堆数据结构的不变性质。
（3）抽象性。
（4）过程抽象。
（5）抽象数据类型。
三、习题
（1）习题1：实现基于堆的优先级队列，尽可能的提高运行速度。
为了提高向上调整堆的速度，在x[0]放置哨兵==当前插入的元素。省去了每次都判断i>1，向上调整堆结束：x[p] <= x[i]。代码如下：
void insert(T t) //向上调整堆
{
int i, p;
x[++n] = t; //插入的元素放到最后
x[0]=t;
for (i = n; x[p=i/2] > x[i]; i = p)
swap(x[p], x[i]);
}
（2）习题4：如何使用优先级队列解决下列问题：
a、构件霍夫曼码；
b、计算大型浮点数集合的和；
c、在存有10亿个数的文件中找到最大的100W个数；
d、将多个较小的有序文件归并为一个较大的有序文件；
解答：
a、构造哈夫曼树时候，需要选取当前数组的两个最小值，删除两个最小值，并将计算之和插入原来数组，采用堆，初建堆，两次调用选取最小值的函数。计算之和之后，调用插入堆并调整堆；b、如果将较小浮点数和较大浮点数相加可能造成丢失精度。所以每次取最小的两个相加。然后将和插入数组集合。最后剩下一个就是所有浮点数的和；c、典型的topK；d、将所有小文件要插入的当前值组成一个堆。取堆最小值，插入排序数组。调整堆。然后插入该小文件下一个元素（无后继则不操作）。
（3）习题7：在一些计算机上，除以2求当前范围的中点是二分搜索程序中开销最大的部分。假设我们已经正确构建了待搜索的数组，说明如何使用乘以2的操作来替代除法。给出建立并搜索这样一个数组的算法。
修改后的二分搜索从i=1开始，每次迭代将i设置为2i或2i+1.元素x[1]包含中值，x[2]包含第一个四分位值，x[3]包含第三个四分位值，等等。一种能在O(n)时间内将n元有序数组调整为“堆搜索”顺序的算法。作为该方法的先驱，考虑把一个2^k-1元的有序数组a拷贝到一个“堆搜索”数组b中：a中奇数位的元素按顺序放到b的后半部分，模4余2位置的元素按顺序放到b中剩余部分的后半部分，等等。