堆排序(Heapsort)是指利用堆积树(堆)这种数据结构所设计的一种排序算法，它是选择排序的一种。可以利用数组的特点快速定位指定索引的元素。堆分为大根堆和小根堆，是完全二叉树。大根堆的要求是每个节点的值都不大于其父节点的值，即A[PARENT[i]] >= A[i]。在数组的非降序排序中，需要使用的就是大根堆，因为根据大根堆的要求可知，最大的值一定在堆顶。

• 中文名 堆排序
• 外文名 Heapsort
• 类别 排序算法
• 发明人 罗伯特·弗洛伊德
• 起源于 罗伯特·弗洛伊德

起源

　　1991年的计算机先驱奖获得者、斯坦福大学计算机科学系教授罗伯特·弗洛伊德(Robert W.Floyd)和威廉姆斯(J.Williams)在1964年共同发明了著名的堆排序算法( Heap Sort )

堆

定义

　　n个关键字序列Kl，K2，…，Kn称为(Heap)，当且仅当该序列满足如下性质(简称为堆性质):

　　(1)ki<=k(2i)且ki<=k(2i+1)(1≤i≤ n/2)，当然，这是小根堆，大根堆则换成>=号(2)ki>=k(2i)且ki>=k(2i+1)(1≤i≤ n/2)。k(i)相当于二叉树的非叶子结点，K(2i)则是左子节点，k(2i+1)是右子节点

　　若将此序列所存储的向量R[1..n]看做是一棵完全二叉树的存储结构，则堆实质上是满足如下性质的完全二叉树:树中任一非叶子结点的关键字均不大于(或不小于)其左右孩子(若存在)结点的关键字。

　　【例】关键字序列(10，15，56，25，30，70)和(70，56，30，25，15，10)分别满足堆性质(1)和(2)，故它们均是堆，其对应的完全二叉树分别如小根堆示例和大根堆示例所示。

　　大根堆和小根堆:根结点(亦称为堆顶)的关键字是堆里所有结点关键字中最小者的堆称为小根堆，又称最小堆。根结点(亦称为堆顶)的关键字是堆里所有结点关键字中最大者，称为大根堆，又称最大堆。注意:①堆中任一子树亦是堆。②以上讨论的堆实际上是二叉堆(Binary Heap)，类似地可定义k叉堆。

高度

　　堆可以被看成是一棵树，结点在堆中的高度可以被定义为从本结点到叶子结点的最长简单下降路径上边的数目;定义堆的高度为树根的高度。我们将看到，堆结构上的一些基本操作的运行时间至多是与树的高度成正比，为O(lgn)。

简介

　　堆排序利用了大根堆(或小根堆)堆顶记录的关键字最大(或最小)这一特征，使得在当前无序区中选取最大(或最小)关键字的记录变得简单。

　　(1)用大根堆排序的基本思想

　　① 先将初始文件R[1..n]建成一个大根堆，此堆为初始的无序区

　　② 再将关键字最大的记录R[1](即堆顶)和无序区的最后一个记录R[n]交换，由此得到新的无序区R[1..n-1]和有序区R[n]，且满足R[1..n-1].keys≤R[n].key

　　③由于交换后新的根R[1]可能违反堆性质，故应将当前无序区R[1..n-1]调整为堆。然后再次将R[1..n-1]中关键字最大的记录R[1]和该区间的最后一个记录R[n-1]交换，由此得到新的无序区R[1..n-2]和有序区R[n-1..n]，且仍满足关系R[1..n-2].keys≤R[n-1..n].keys，同样要将R[1..n-2]调整为堆。

　　……

　　直到无序区只有一个元素为止。

　　(2)大根堆排序算法的基本操作:

　　①建堆，建堆是不断调整堆的过程，从len/2处开始调整，一直到第一个节点，此处len是堆中元素的个数。建堆的过程是线性的过程，从len/2到0处一直调用调整堆的过程，相当于o(h1)+o(h2)…+o(hlen/2) 其中h表示节点的深度，len/2表示节点的个数，这是一个求和的过程，结果是线性的O(n)。

　　②调整堆:调整堆在构建堆的过程中会用到，而且在堆排序过程中也会用到。利用的思想是比较节点i和它的孩子节点left(i),right(i)，选出三者最大(或者最小)者，如果最大(小)值不是节点i而是它的一个孩子节点，那边交互节点i和该节点，然后再调用调整堆过程，这是一个递归的过程。调整堆的过程时间复杂度与堆的深度有关系，是lgn的操作，因为是沿着深度方向进行调整的。

　　③堆排序:堆排序是利用上面的两个过程来进行的。首先是根据元素构建堆。然后将堆的根节点取出(一般是与最后一个节点进行交换)，将前面len-1个节点继续进行堆调整的过程，然后再将根节点取出，这样一直到所有节点都取出。堆排序过程的时间复杂度是O(nlgn)。因为建堆的时间复杂度是O(n)(调用一次);调整堆的时间复杂度是lgn，调用了n-1次，所以堆排序的时间复杂度是O(nlgn)

注意

　　①只需做n-1趟排序，选出较大的n-1个关键字即可以使得文件递增有序。

　　②用小根堆排序与利用大根堆类似，只不过其排序结果是递减有序的。堆排序和直接选择排序相反:在任何时刻堆排序中无序区总是在有序区之前，且有序区是在原向量的尾部由后往前逐步扩大至整个向量为止

特点

　　堆排序(HeapSort)是一树形选择排序。堆排序的特点是:在排序过程中，将R[l..n]看成是一棵完全二叉树的顺序存储结构，利用完全二叉树中双亲结点和孩子结点之间的内在关系(参见二叉树的顺序存储结构)，在当前无序区中选择关键字最大(或最小)的记录

算法分析

　　堆排序的时间，主要由建立初始堆和反复重建堆这两部分的时间开销构成，它们均是通过调用Heapify实现的。

平均性能

　　O(N*logN)。

其他性能

　　由于建初始堆所需的比较次数较多，所以堆排序不适宜于记录数较少的文件。

　　堆排序是就地排序，辅助空间为O(1).

　　它是不稳定的排序方法。(排序的稳定性是指如果在排序的序列中，存在前后相同的两个元素的话，排序前 和排序后他们的相对位置不发生变化)

示例代码

Pascal代码

　　示例1:

　　const max=100000;

　　var

　　a:array[0..max] of longint;

　　n,i,tot,t:longint;

　　procedure down(i:longint);

　　var j,t:longint;

　　begin

　　while i<=tot shr 1 do

　　begin

　　j:=2*i;

　　if (j<tot) and (a[j+1]<a[j]) then inc(j);

　　if a[i]>a[j] then

　　begin

　　t:=a[i];

　　a[i]:=a[j];

　　a[j]:=t;

　　i:=j;

　　end

　　else break;

　　end;

　　end;

　　begin

　　readln(n);

　　for i:=1 to n do read(a[i]);

　　tot:=n;

　　for i:=n shr 1 downto 1 do down(i);

　　for i:=1 to n do

　　begin

　　t:=a[1]; a[1]:=a[tot]; a[tot]:=t;

　　dec(tot);

　　down(1);

　　end;

　　for i:=n downto 1 do write(a[i],' ');

　　end.

　　示例2:

　　const max=100000;

　　var

　　a:array[0..max] of longint;

　　n,i,tot,t:longint;

　　procedure down(i:longint);

　　var j,t:longint;

　　begin

　　while i<=tot shr 1 do

　　begin

　　j:=2*i;

　　if (j<tot) and (a[j+1]<a[j]) then inc(j);

　　if a[i]>a[j] then

　　begin

　　t:=a[i];

　　a[i]:=a[j];

　　a[j]:=t;

　　i:=j;

　　end

　　else break;

　　end;

　　end;

　　procedure up(i:longint);

　　var j,t:longint;

　　begin

　　j:=i;

　　while (j>1) and (a[j]<a[j shr 1]) do

　　begin

　　t:=a[j];

　　a[j]:=a[j shr 1];

　　a[j shr 1]:=t;

　　j:=j shr 1;

　　end;

　　end;

　　begin

　　readln(n);

　　for i:=1 to n do

　　begin

　　read(a[i]);

　　up(i);

　　end;

　　tot:=n;

　　for i:=1 to n do

　　begin

　　t:=a[1]; a[1]:=a[tot]; a[tot]:=t;

　　dec(tot);

　　down(1);

　　end;

　　for i:=n downto 1 do write(a[i],' ');

　　end.