堆排序原理及分析
起源
1991年計算機先驅獎獲得者、斯坦福大學計算機科學系教授
羅伯特·弗洛伊德(Robert W．Floyd）和威廉姆斯(J．Williams）在1964年共同發明了著名的堆排序算法（ Heap Sort )
堆排序[1]
“堆”定義
n個關鍵字序列Kl，K2，…，Kn稱為（Heap），當且僅當該序列滿足如下性質（簡稱為堆性質）：
(1)ki<=k(2i）且ki<=k(2i+1)(1≤i≤ n），當然，這是小根堆，大根堆則換成>=号。//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）大根堆排序算法的基本操作：
① 初始化操作：将R[1..n]構造為初始堆；
② 每一趟排序的基本操作：将目前無序區的堆頂記錄R[1]和該區間的最後一個記錄交換，然後将新的無序區調整為堆（亦稱重建堆）。
注意：
①隻需做n-1趟排序，選出較大的n-1個
即可以使得檔案遞增有序。
②用小根堆排序與利用大根堆類似，隻不過其排序結果是遞減有序的。堆排序和直接
選擇排序相反：在任何時刻堆排序中無序區總是在有序區之前，且有序區是在原向量的尾部由後往前逐漸擴大至整個向量為止
特點
堆排序（HeapSort）是一樹形
。堆排序的特點是：在排序過程中，将R[l..n]看成是一棵
順序存儲結構，利用完全二叉樹中雙親結點和孩子結點之間的内在關系（參見二叉樹的順序存儲結構），在目前無序區中選擇
最大（或最小）的記錄
堆排序與直接選擇排序的差別
直接
中，為了從R[1..n]中選出關鍵字最小的記錄，必須進行n-1次比較，然後在R[2..n]中選出關鍵字最小的記錄，又需要做n-2次比較。事實上，後面的n-2次比較中，有許多比較可能在前面的n-1次比較中已經做過，但由于前一趟排序時未保留這些比較結果，是以後一趟排序時又重複執行了這些比較操作。
堆排序可通過
樹形結構儲存部分比較結果，可減少比較次數。
算法分析
堆排序的時間，主要由建立初始堆和反複重建堆這兩部分的時間開銷構成，它們均是通過調用Heapify實作的。
堆排序的最壞
時間複雜度為O(nlogn)。堆序的平均性能較接近于最壞性能。
由于建初始堆所需的比較次數較多，是以堆排序不适宜于記錄數較少的檔案。
堆排序是就地排序，輔助空間為O(1），
它是不穩定的排序方法。
算法描述
C語言描述
// array是待調整的堆
數組，i是待調整的數組元素的位置，nlength是數組的長度
//本函數功能是：根據
array建構大根堆
void HeapAdjust(int array[], int i, int nLength)
{
int nChild;
int nTemp;
for (nTemp = array[i]; 2 * i + 1 < nLength; i = nChild)
// 子結點的位置=2*（父結點位置）+ 1
nChild = 2 * i + 1;
// 得到子結點中較大的結點
if (nChild < nLength - 1 && array[nChild + 1] > array[nChild])
++nChild;
// 如果較大的子結點大于
父結點那麼把較大的子結點往上移動，替換它的父結點
if (nTemp < array[nChild])
array[i] = array[nChild];
}else{
// 否則退出循環
break;
}
// 最後把需要調整的元素值放到合适的位置
array[nChild]= nTemp;
// 堆排序算法
void HeapSort(int array[],int length)
// 調整序列的前半部分元素，調整完之後第一個元素是序列的最大的元素
for (int i = length / 2 - 1; i >= 0; --i)
HeapAdjust(array, i, length);
// 從最後一個元素開始對序列進行調整，不斷的縮小調整的範圍直到第一個元素
for (int i = length - 1; i > 0; --i)
// 把第一個元素和目前的最後一個元素交換，
// 保證目前的最後一個位置的元素都是在現在的這個序列之中最大的
Swap(&array[0], &array[i]);
// 不斷縮小調整heap的範圍，每一次調整完畢保證第一個元素是目前序列的最大值
HeapAdjust(array, 0, i);
堆排序算法（C++描述）
#define MAX 100//
資料元素的最大個數
typedef struct
int r[MAX];
int length;
}SqList;//定義一個線性表用于存放
void HeapAdjust(SqList &L,int s,int m)
{//已知L.r[s...m]中記錄除L.r[s]外均滿足堆的定義，本函數用于使L.r[s...m]成為一個大頂堆
int j;
int e=L.r[s];
for(j=2*s;j<=m;j*=2)
if(j<M&&L.R[J]<L.R[J+1]) ++j;
if(e>=L.r[j]) break;
L.r[s]=L.r[j];
s=j;
L.r[s]=e;
void HeapSort(SqList &L)
{//對
順序表L進行堆排序
int i,e;
for(i=L.length/2;i>0;i--)
HeapAdjust(L,i,L.length);
for(i=L.length;i>1;i--)
{//将大頂堆的頂記錄和最後一個記錄互相交換
e=L.r[1];
L.r[1]=L.r[i];
L.r[i]=e;
HeapAdjust(L,1,i-1);
因為構造初始堆必須使用到調整堆的操作，先讨論Heapify的實作，再讨論如何構造初始堆（即BuildHeap的實作）Heapify函數思想方法
每趟排序開始前R[l..i]是以R[1]為根的堆，在R[1]與R交換後，新的無序區R[1..i-1]中隻有R[1]的值發生了變化，故除R[1]可能違反堆性質外，其餘任何結點為根的子樹均是堆。是以，當被調整區間是R[low..high]時，隻須調整以R[low]為根的樹即可。
"篩選法"調整堆
R[low]的左、右子樹（若存在）均已是堆，這兩棵子樹的根R[2low]和R[2low+1]分别是各自子樹中
最大的結點。若R[low].key不小于這兩個孩子結點的
，則R[low]未違反堆[性質，以R[low]為根的樹已是堆，無須調整；否則必須将R[low]和它的兩個孩子結點中關鍵字較大者進行交換，即R[low]與R[large](R[large].key=max(R[2low].key，R[2low+1].key））交換。交換後又可能使結點R[large]違反堆性質，同樣由于該結點的兩棵子樹（若存在）仍然是堆，故可重複上述的調整過程，對以R[large]為根的
樹進行調整。此過程直至目前被調整的結點已滿足性質，或者該結點已是葉子為止。上述過程就象過篩子一樣，把較小的
逐層篩下去，而将較大的關鍵字逐層選上來。是以，有人将此方法稱為"篩選法"。
BuildHeap的實作
要将初始檔案R[l..n]調整為一個大根堆，就必須将它所對應的
中以每一結點為根的子樹都調整為堆。
顯然隻有一個結點的樹是堆，而在
中，所有序号大于n/2的結點都是葉子，是以以這些結點為根的子樹均已是堆。這樣，我們隻需依次将以序号為n/2，…，1的結點作為根的子樹都調整為堆即可。
Heapify函數算法執行個體
#include
inline int LEFT(int i);
inline int RIGHT(int i);
inline int PARENT(int i);
void MAX_HEAPIFY(int A[],int heap_size,int i);
void BUILD_MAX_HEAP(int A[],int heap_size);
void HEAPSORT(int A[],int heap_size);
void output(int A[],int size);
int main()
FILE *fin;
int m,size,i;
fin = fopen("arrayin","r");
int* a;
fscanf(fin," %d",&size);
a = (int *)malloc(size + 1);
a[0]=size;
for(i = 1;i <= size; i++ )
fscanf(fin," %d",&m);
a[i]= m;
HEAPSORT(a,a[0]);
printf("$$$$$$$$$$The Result$$$$$$$$\n");
output(a,a[0]);
free(a);
return 0;
inline int LEFT(int i)
return 2 * i;
inline int RIGHT(int i)
return 2 * i + 1;
inline int PARENT(int i)
return i / 2;
void MAX_HEAPIFY(int A[],int heap_size,int i)
int temp,largest,l,r;
largest = i;
l = LEFT(i);
r = RIGHT(i);
if ((l <= heap_size) && (A[l] > A[largest])) largest = l;
if ((r<= heap_size) && (A[r] > A[largest])) largest = r;
if (largest != i)
temp = A[largest];
A[largest] = A[i];
A[i]= temp;
MAX_HEAPIFY(A[],heap_size,largest);
void BUILD_MAX_HEAP(int A[],int heap_size)
int i;
for (i = heap_size / 2;i >= 1;i--) MAX_HEAPIFY(A,heap_size,i);
void HEAPSORT(int A[],int heap_size)
BUILD_MAX_HEAP(A,heap_size);
for (i = heap_size;i >= 2; i--)
int temp;
temp = A[1];
A[1] = A[heap_size];
A[heap_size]= temp;
MAX_HEAPIFY(A,i-1,1);
void output(int A[],int size)
int i = 1;
FILE *out = fopen("resultin","w+");
for (; i <= size; i++)
printf("%d ",A);
fprintf(out,"%d ",A);
printf("\n");
Pascal/Delphi描述
const
max=100;
type
arr=array[1..max] of integer;
var
a:arr;
i,n,temp:integer;
procedure heap(var r:arr;nn,ii:integer); //之是以重新定義r
而不是在a數組上修改，是為了能同時操作不同的數組
x,i,j:integer;
begin
i:=ii;
x:=r[ii];//把待調整的節點值暫存起來。
j:=ii shl 1;//j 為 ii 的左孩子編号，初始時假設它比右孩子的值大。
while j<=nn do
if (j+1<=nn) and (r[j]<r[j+1]) then //必須是j+1，因為j=nn時，j+1>nn，會影響已排過的節點！
inc(j);//j 為值大的那個孩子的節點編号。
if x<r[j] then//調整。
r[i]:=r[j];
i:=j;
j:=i shl 1
end
else j:=nn+1//故意讓 j 超出範圍，終止循環。
end;
r[i]:=x;//調整到最終位置。
readln(n);
for i:=1 to n do
read(a[i]);
writeln;
for i:=n shr 1 downto 1 do
heap(a,n,i);//建立初始堆，且産生最大值 A[1]。
for i:=n downto 2 do//将目前最大值交換到最終位置上，再對前 i-1 個數調整。
temp:=a[1];
a[1]:=a[i];
a[i]:=temp;
heap(a,i-1,1)
write(a[i]:4)
end.
Pascal源代碼
i,n:integer;
a:array[0..100] of integer;
procedure swap(var a,b:integer);
var t:integer;
begin t:=a;a:=b;b:=t;
procedure heapsort(i,m:integer);
t:=i*2;
while t<=m do
if (t<m) and (a[t]>a[t+1]) then inc(t);
if a[i]>a[t] then begin swap(a[i],a[t]);i:=t;t:=2*i; end
else break;
for i:=1 to n do read(a[i]);
for i:=n div 2 downto 1 do heapsort(i,n);
for i:=n downto 2 do
write(a[1],' ');
heapsort(1,i-1);
writeln(a[1]);
JAVA描述
public class HeapSortTest {
/*
* 将
調整為小根堆，即由小到大排序
*/
public static int[] heap = new int[] { 1,3,7,5,2,8,4,6,10,9};
public static void main(String[] args) {
* 建立堆（對該堆進行簡單的排序）
CreateHeap();
for (int i = heap.length - 1; 0 < i; i--) {
temp = heap[0];
heap[0] = heap[i];
heap[i] = temp;
* 展示每次排序後的結果
for (int j = 0; j < heap.length; j++) {
System.out.print(heap[j] + " ");
System.out.println();//換行
* 從堆頂進行調整，使未排序堆中最大關鍵字到堆頂
AdjustHeap(0,i);
* 調整堆使其堆頂為未排序堆中最大關鍵字
public static void AdjustHeap(int location,int unSortlength) {
int tempLoc;
* 確定左右節點存在
if ((tempLoc = (location + 1) * 2) < unSortlength) {
* 判斷左右節點大小
if (heap[tempLoc] >= heap[tempLoc - 1]) {
* 判斷父節點與子節點的大小，若父節點小，則與大的子節點換位
if (heap[location] < heap[tempLoc]) {
temp = heap[location];
heap[location] = heap[tempLoc];
heap[tempLoc] = temp;
*
遞歸法對換位後的子節點及其子節點進行調整
AdjustHeap(tempLoc,unSortlength);
} else {
* 左節點大于右節點
if (heap[location] < heap[tempLoc - 1]) {
heap[location] = heap[tempLoc - 1];
heap[tempLoc - 1] = temp;
* 遞歸法對換位後的子節點及其子節點進行調整
AdjustHeap(tempLoc - 1,unSortlength);
* 確定左節點存在
else if ((tempLoc = (location + 1) * 2 - 1) < unSortlength) {
* 與左
節點進行比較
左子節點大于父節點，将兩者進行換位
public static void CreateHeap() {
for (int i = heap.length - 1; i >= 0; i--) {
AdjustHeap(i,heap.length);
c++描述（降序）
/* 這是經過優化的代碼。一般都用大根堆，但是如果用小根堆實作，每次都将最小的元素放到最後一個，可以省一半空間。用c
是因為我寫一道題目需要給c數組排序……直接粘過去，偷懶一下 &^_^& */
#include<iostream>
using namespace std;
int c[1000];
int n,m;
void check(int i)
int min;
if(m>=i*2+1) //不能用n，因為需要排序的元素個數在不斷變化
if(c[i*2+1]<c[i*2])
min=i*2+1;
else
min=i*2;
if(c[min]<c[i])
swap(c[i],c[min]);
check(min);
} //這幾行也可以換成判斷然後交換c[i]和c[i*2+1]，又可以省去幾行。哈哈。
if(m>=i*2 && c[i*2]<c[i])
swap(c[i*2],c[i]);
check(i*2);
//check函數用來維持小根堆
void tree()
m=n;
for(int i=m/2;i>=1;i--)
check(i);
while(m!=1)
swap(c[1],c[m]); //将最小的元素放到最後，這個元素以後的元素就是有序的，不用參加排序了
m--;
check(1);
//tree函數用來建堆
cin>>n;
for(int i=1;i<=n;i++)
cin>>c[i];
tree();
for(i=1;i<=n;i++)
cout<<c[i]<<' ';
cout<<endl;
system("pause"); //為了友善觀察結果才寫的這一行，送出題目的時候一定要删掉！！！
AAuto語言描述
io.open();//打開控制台
*-------------------------------------------------------
* 堆排序（ 原地排序 )
是
。
索引總是以2倍的形式遞增，從上到下從左到右順序遞增
[1]
∧
[2] [3]
∧ ∧
[4] [5] [6] [7]
是以可以用
來表示
設 heap= {}
heap[1] = 29;
heap[2] = 19;
heap[3] = 18;
heap[4] = 9;
heap[5] = 8;
heap[6] = 7;
heap[7] = 6;
則 heap如下排列 {29;19;18;9;8;7;6}
29
19 18
9 9 7 6
有小根堆，大根堆，大根堆最大的元素在頂部，所有元素按索引排序。
getParentIndex = function(i){
//
的父子索引總是以2倍的形式遞增、堆左邊索引是2的n次方。
return math.floor(i/2)//是以除2總是能向上倒退一層到父節點的索引。
getLeftNodeIndex = function(i){
//父層到子層，總是一變二，是以索引也增加2倍
return 2*i
getRightNodeIndex = function(i){
return 2*i+1
假定一個
A的元素i，假定getLeftNodeIndex[i],getRightNodeIndex[i]都是最大堆。
如果array[i]小于其子女，則調節array[i]，使之下降。
max_heapify = function(array,i){
var l = getLeftNodeIndex(i);
var r = getRightNodeIndex(i);
var largest;
if( ( l<=array.heapsize ) and( array[l] > array[i]) )
largest = l;//
樹比較大
else{
largest = i;//父節點比較大
if( ( r<=array.heapsize ) and( array[r] > array[largest]) )
largest = r;//右子樹比較大
//如果array[i]小于其子女，則調節array[i]，使之下降。
if( largest != i){
var exchange = array[i]
array[i] = array[largest]
array[largest] = exchange;
max_heapify(array,largest);//現在子樹largest是最大的了
對于
A，最後一個頁節點索引為#A
#A的父節點為 math.floor(#A/2) ，而且是最後一個父節點。而之後都是葉節點。
是以，我們從最後一個父節點開始，從右至左，自下而上調用max_heapify檢查所有的堆。使之符合
定義.
如此：小的通過max_heapify函數的
遞歸調用一降到底，大的數通過build_max_heap的for循環逐漸上升到頂，清升而濁降。
//建堆
build_max_heap = function(array){
array.heapsize = #array;
for(i=math.floor(#array/2);1;-1){
max_heapify(array,i);
堆建好了，根
一定比子結點大。
但是左邊的不一定比右邊的大，因為
不比較左右子樹。
而且在不同的子
裡，他們也沒有排序關系
io.print( table.tostring(array) ) //輸出看一下，整體上仍然是亂的
堆雖然不是完全線性有序的
，但是根節點總是最大的元素。
通常用于實作 高效的優先級隊列
//那麼下面我們要利用建好的堆來排序
heap_sort = function(array){
build_max_heap(array)//建堆
//現在array[1]是根節點了，并且一定是最大的
//我們把最大的放在
最右側，後把最右側較小的元素放到根節點來破壞
，再用max_heapify來修複堆取到下一個最大的數
//不斷循環此過程，不斷的将最大的元素移到右側，而堆向左收縮，就達到了排序的效果
for(sorted=#array;2;-1){
var max = array[1]
array[1] = array[sorted] //把小的移到
的頂部來破壞堆定義
array[sorted] = max;//把最大的移到右側已排序的數組中
array.heapsize--;
max_heapify(array,1);//修複
根節點，取下一個最大數
//終于排序好了輸出看一下
io.print("----------------")
io.print("堆排序")
array ={2;46;5;17;1;2;3;99;12;56;66;21};
heap_sort(array)
//輸出結果
for(i=1;#array;1){
io.print( array[i] )
排序算法的穩定性：保證排序前2個相等的數其在序列的前後位置順序和排序後它們兩個的前後位置順序相同
穩定
：
冒泡排序 插入排序 合并排序不穩定
：堆排序 快速排序
execute("pause") //按
任意鍵繼續
io.close();//關閉控制台
js語言描述
//5000個無序随機裡取最大的50個數
//定義
var heap={};
//大
，從1-1000000取5000個随機數
heap.arr=[];
for(var i=0;i<5000;i++){
heap.arr.push(Math.floor(1000000*Math.random())+1);
//取前50個數作為堆
heap.arrTemp=heap.arr.slice(0,50).sort(function(a,b){
return a-b;
});
//無序
裡挨個與堆的最小數判斷，大則入堆，堆重新排序，傳回50個最大的數
heap.j=50;
(function(){
while(heap.j<5000){
if(heap.arr[heap.j]>heap.arrTemp[0]){
heap.arrTemp.splice(0,1,heap.arr[heap.j]);
heap.arrTemp.sort(function(a,b){
heap.j++;
return heap.arrTemp;
})();