堆排序就是把最大堆堆頂?shù)淖畲髷?shù)取出毒坛，將剩余的堆繼續(xù)調整為最大堆，再次將堆頂?shù)淖畲髷?shù)取出(最大堆調整的遞歸運算)，這個過程持續(xù)到剩余數(shù)只有一個時結束辨泳。在堆中定義以下幾種操作：
最大堆調整（Max-Heapify):
將堆的末端子節(jié)點作調整，使得子節(jié)點永遠小于父節(jié)點
創(chuàng)建最大堆（Build-Max-Heap):
將堆所有數(shù)據重新排序玖院，使其成為最大堆
堆排序（Heap-Sort):
移除位在第一個數(shù)據的根節(jié)點菠红，并做最大堆調整的遞歸運算
繼續(xù)進行下面的討論前，需要注意的一個問題是：數(shù)組都是 Zero-Based难菌，這就意味著我們的堆數(shù)據結構模型要發(fā)生改變
相應的试溯，幾個計算公式也要作出相應調整：
Parent(i) = floor((i-1)/2)，i 的父節(jié)點下標
Left(i) = 2i + 1郊酒，i 的左子節(jié)點下標
Right(i) = 2(i + 1)遇绞，i 的右子節(jié)點下標
最大堆調整（MAX‐HEAPIFY）的作用是保持最大堆的性質，是創(chuàng)建最大堆的核心子程序燎窘，作用過程如圖所示：
創(chuàng)建最大堆（Build-Max-Heap）的作用是將一個數(shù)組改造成一個最大堆摹闽，接受數(shù)組和堆大小兩個參數(shù)，Build-Max-Heap 將自下而上的調用 Max-Heapify 來改造數(shù)組褐健，建立最大堆付鹿。因為 Max-Heapify 能夠保證下標 i 的結點之后結點都滿足最大堆的性質，所以自下而上的調用 Max-Heapify 能夠在改造過程中保持這一性質蚜迅。如果最大堆的數(shù)量元素是 n舵匾，那么 Build-Max-Heap 從 Parent(n) 開始，往上依次調用 Max-Heapify慢叨。流程如下
堆排序（Heap-Sort）是堆排序的接口算法纽匙，Heap-Sort先調用Build-Max-Heap將數(shù)組改造為最大堆，然后將堆頂和堆底元素交換拍谐，之后將底部上升烛缔，最后重新調用Max-Heapify保持最大堆性質馏段。由于堆頂元素必然是堆中最大的元素，所以一次操作之后践瓷，堆中存在的最大元素被分離出堆院喜，重復n-1次之后，數(shù)組排列完畢晕翠。整個流程如下：
C語言實現(xiàn):
#include <stdio.h>
#include <stdlib.h>
void swap(int *arr,int i, int k)
{
int temp = arr[i];
arr[i] = arr[k];
arr[k] = temp;
}
void max_heapify(int *arr, int start, int end)
{
//建立父節(jié)點下標和子節(jié)點下標
int dad = start;
int son = dad * 2 + 1;
while (son <= end)
{ //若子節(jié)點下標在范圍內才做比較
if (son + 1 <= end && arr[son] < arr[son + 1]) //先比較兩個子節(jié)點大小喷舀，選擇最大的
{
son++;
}
if (arr[dad] > arr[son]) //如果父節(jié)點大于子節(jié)點代表調整完畢,直接跳出
{
return;
}
else
{ //否則交換父子節(jié)點的值再繼續(xù)左右子節(jié)點值得比較
swap(arr,dad, son);
printf("dad=%d--son=%d\n",dad,son);
dad = son;
son = dad * 2 + 1;
}
}
}
void heap_sort(int *arr, int len)
{
int i;
//初始化，i從最后一個父節(jié)點開始調整
for (i = len / 2 - 1; i >= 0; i--)
{
max_heapify(arr, i, len - 1);
}
for (i = len - 1; i > 0; i--)
{
swap(arr,0, i);
max_heapify(arr, 0, i - 1);
}
}
int main(int argc, char const *argv[])
{
int arr[] = {5,3,8,1,6};
int len = sizeof(arr) / sizeof(int);
heap_sort(arr, len);
for (int i = 0; i < len; i++)
{
printf("%d ", arr[i]);
}
printf("\n");
return 0;
}
步驟詳解:
下標0 1 2 3 4
Array={5,3,8,1,6};
Len=5
i=5/2 -1 =1 為最后一個元素的父節(jié)點的下標值
Max_heapity(arr,i,len-1)
i=1 len-1=4 end=4
1 > 6 son=4
dad=4
son=4*2+1=9
9>4 while 第一次結束
i=0
Max_heapity(arr,0,4)
dad=0 ; end=4 son=1
1 < 4
6< 8
son=2
dad=2
son=2*2 +1 =5
5<end=4 while 第二次結束
i=-1 i<0 第一個for循環(huán)結束
第二個for循環(huán)開始
len=5
i=len-1=4
max_heapity(arr,0,3)
dad=0 son=1 end=3
son=3 dad=1
while 第三次結束
i=3 len=5
swap(arr,0,3)
max_heapify(arr,0,2);
dad=0; son=1;end=2
3 < 5
son=2
dad=2
son=2*2+1=5
while 第四次結束
i=2 len=5
max_heapity(arr,0,1)
dad=0; son=1 end=1
i=1 len=5
max_heapity(arr,0,0)
dad=0; son =1
1<0 while跳出
i=0時 第二個for循序結束
最終結果: 13 5 6 8
