堆排序（Heap Sort）是利用称为“堆”的结构所具有的性质，从堆中逐次得到待排序记录中关键字最小（最大）的记录，来完成排序。

（1）堆的定义及性质

1 堆的定义

堆的定义如下：一个由n个记录的线性序列（R1，R2，…，Rn），其相应的关键字序列为（K1，K2，…，Kn），若满足如下条件：

则上述线性序列称之为堆。

本节只讨论满足上面左式的堆，即小根堆。

2 堆与特殊性质的完全二叉树的对应

若用一维数组存放堆，并把它看成是一棵完全二叉树的顺序存储表示，这样一个堆就对应一棵完全二叉树，树中任一个非叶子结点所对应的记录的关键字均不大于（小于等于）其左、右孩子结点对应记录的关键字的值。

例如，满足堆条件的关键字序列为{14，40，30，50，80，65，50，100 }，它对应的完全二叉树如图9 -3所示。

堆的二叉树表示

显然，14<40，14<30；40<50，40<80；30<65，30<50；50<100，符合堆的定义，因而针对一棵完全二叉树，通过判断该二叉树中任意一个非叶结点所对应记录的关键字是否均小于其左、右孩子结点对应记录的关键字的值，来判断它是否为堆。

3 堆的性质

对于小根堆，具有如下性质：

a．根结点是完全二叉树所有结点对应的记录中关键字最小的。

b．树中任何一棵子树也对应一个子堆。

（2）堆排序的基本思想

对一组待排序的有n个记录的记录序列，按照它们的关键字的大小构造一个堆，输出堆顶记录，对剩余的n-1个记录序列再调整为一个新堆，输出堆顶记录……直到输出第n 个记录。

通过以上分析可以把堆排序归纳为以下两种操作：

1.如何将一个无序的记录序列构造成一个初始堆。

2.如何将一个堆逐次取走堆顶元素（记录）后，将剩余记录重新调整成为一个新堆。

（3）筛选算法及算法步骤

筛选算法：在一棵完全二叉树中，若根结点的左右子树都分别对应一个堆， 通过一系列自顶向下的调整步骤，使该二叉树对应一个堆。自顶向下的调整过程称为筛选。筛选算法也可针对完全二叉中的某一棵子树。

算法步骤如下：

1.设一个无序的记录序列已建成一个堆，设堆中有n个记录，输出堆顶元素，以堆中最后一个记录取代。n-1个记录已不是堆，但左右子树仍为堆。

2.堆顶记录的关键字与左、右子树根结点记录关键字的较小者比较，若大于较小者,堆顶记录与较小者交换。

3.交换后，若破坏了左或右子堆，则对相应子树进行上述同样处理，直到建成n-1个记录的堆。

4.对n-1个记录的堆，重复上述①、②、③的操作，直至输出全部记录，得到n个记录由小到大的有序序列。

图9-4是输出堆顶元素后调整并构造新堆的过程。

输出堆顶元素后并调整成新堆的过程

（4）利用筛选法建立堆

利用“筛选”过程，很容易完成对一个无序的记录序列建成一个堆，建堆过程可以归结为一个自下至顶建立子堆，子堆由小到大的反复“筛选”过程。

具体做法是：

1.把将要排序的序列看成一棵完全二叉树。

2.从最后一个非叶结点（序号 k=n/2）开始，依次取结点k，k-1，…，直到第一个结点，逐次以每一个结点作为它的左，右子堆的根结点进行“筛选”，就完成了建堆的过程。

例如关键字序列{40，80，65，100，14，30，55，50}如图9-5所示。

建堆过程

筛选算法

	void heapshift(NODE a[],int i,int n)	/*设记录序列存放在a[1],...a[n]中，其中a[i],...a[n]中存放的记录除a[i]外，其它记录的关键字的序列满足堆的条件，对a[i]进行筛选，使a[i],...,a[n]中的记录的关键字序列成为堆*/	{	 NODE temp;int j;	 temp=a[i]; /*保存待筛选的根结点*/	 j=2*i ; /*根结点的左儿子的下标（序号）*/	 while(j<=n) /*最多调整到最后一个非叶结点*/	 {	 if(j+1<=n&&a[j].key>a[j+1].key)	 j++; /*若存在右儿子，则使j指向左右儿子中记录关键字较小者*/	 if(temp.key>a[j].key)	 {	 a[i]=a[j]; /*把较小的子结点的记录调整到它的父结点的位置*/	 i=j; /*i是被调整了的子树的根的下标，准备对子树进行筛选*/	 j=2*i; /*j是子树根结点的左儿子的下标*/	 }	 else	 break; /*已经满足堆的条件，筛选结束*/	 }	 a[i]=temp; /*原根结点的记录筛选到位*/	}

堆排序

	void heapsort(NODE a[],int n)	/*对存放在a[1]--a[n]中的序列进行堆排序*/	{	 int i;	 NODE temp;	 for(i=n/2;i>=1;i--)	 heapshift(a,i,n); /*从最后一个非叶结点开始从后向前筛选建堆*/	 for(i=n;i>1;i--)	 {	 temp=a[1];a[1]=a[i];a[i]=temp; /*将最小值与当前筛选序列的最后一个元素互换*/	 heapshift(a,1,i-1); /*在a[1]-a[i-1]之间继续筛选*/	 }	}

堆排序的时间复杂度为O(log 2 n)是一种不稳定的排序方法.算法中堆顶元素依次放到数组元素a[n]，a[n-1]，…，a[1]，按记录关键字由大到小排好序,不需要为输出的记录另外开辟存储空间。