我們有意調(diào)整了排序的順序饥伊，最后講這個堆排序葵姥。不是因?yàn)樗茈y荷鼠，而是它涉及到了基本的數(shù)據(jù)結(jié)構(gòu)知識。
# 以下py版摘自百度百科
def big_endian(arr,start,end):
root=start
child=root*2+1 #左孩子
while child<=end:
#孩子比最后一個節(jié)點(diǎn)還大榔幸，也就意味著最后一個葉子節(jié)點(diǎn)了允乐，就得跳出去一次循環(huán)矮嫉，已經(jīng)調(diào)整完畢
if child+1<=end and arr[child]<arr[child+1]:
#為了始終讓其跟子元素的較大值比較，如果右邊大就左換右牍疏，左邊大的話就默認(rèn)
child+=1
if arr[root]<arr[child]:
#父節(jié)點(diǎn)小于子節(jié)點(diǎn)直接交換位置蠢笋，同時坐標(biāo)也得換，這樣下次循環(huán)可以準(zhǔn)確判斷：是否為最底層鳞陨，
#是不是調(diào)整完畢
arr[root],arr[child]=arr[child],arr[root]
root=child
child=root*2+1
else:
break
def heap_sort(arr): #無序區(qū)大根堆排序
first=len(arr)//2 - 1
for start in range(first,-1,-1):
#從下到上昨寞，從左到右對每個節(jié)點(diǎn)進(jìn)行調(diào)整，循環(huán)得到非葉子節(jié)點(diǎn)
big_endian(arr,start,len(arr)-1) #去調(diào)整所有的節(jié)點(diǎn)
for end in range(len(arr)-1,0,-1):
arr[0],arr[end]=arr[end],arr[0] #頂部尾部互換位置
big_endian(arr,0,end-1) #重新調(diào)整子節(jié)點(diǎn)的順序厦滤，從頂開始調(diào)整
return arr
堆援岩，又名“優(yōu)先隊(duì)列”，是一個帶有優(yōu)先級（就是一定順序）的隊(duì)列掏导，而隊(duì)列則是一種基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)享怀，它的特點(diǎn)是“先進(jìn)先出”，i.e.趟咆，先進(jìn)入隊(duì)列的元素添瓷，在做移除操作時會被首先移除出隊(duì)列。其實(shí)值纱，優(yōu)先隊(duì)列這種隊(duì)列仰坦，并沒有說最先進(jìn)入的會被最先移除，因?yàn)閹в幸欢ǖ捻樞蚣拼疲紫冗M(jìn)入的元素也會根據(jù)要求放到合適的位置，而不是最前端玫霎，而刪除時凿滤，假設(shè)是默認(rèn)刪除，會刪除最上方的元素庶近。
我們的堆翁脆，一般情況下都是二叉堆，就是由完全二叉樹構(gòu)成的對象鼻种。二叉樹是一種樹形結(jié)構(gòu)反番，每個父節(jié)點(diǎn)只有2個子節(jié)點(diǎn)；而完全二叉樹則是說叉钥，在排下一個子節(jié)點(diǎn)時罢缸，必須保證這一層之前所有的位置都有節(jié)點(diǎn)。
這樣的結(jié)構(gòu)就會有以下幾個特點(diǎn)投队，
- 假設(shè)一個元素的編號是 i枫疆，一個元素的2個子節(jié)點(diǎn)——左孩子和右孩子分別是 2i 和 2i+1。
- 其父節(jié)點(diǎn)的編號是 i/2敷鸦，是向下取整的息楔。
所以寝贡，當(dāng)我們構(gòu)建一個（最小）二叉堆時值依，我們首先需要一個基本數(shù)據(jù)結(jié)構(gòu)——描述堆的struct或者class：
template <typename T>
struct Heap
{
int Capacity; //描述堆的能力圃泡，i.e.，堆一共能放幾個數(shù)
int Size; //堆目前放了幾個數(shù)
T *elements; //一個放置元素的數(shù)組
};
而我們在使用的時候愿险，可以這樣定義一下：
typedef struct Heap *PriorityQueue;
就會有一個指向此優(yōu)先隊(duì)列的指針颇蜡。
而初始化這個優(yōu)先隊(duì)列也很簡單，給指向優(yōu)先隊(duì)列的指針一個空間拯啦，給放置元素的數(shù)組開辟一個空間澡匪，給結(jié)構(gòu)Heap一個初始值：
template<typename T>
PriorityQueue Initialize( int MaxSize )
{
PriorityQueue H;
H = malloc( sizeof( struct Heap ) ); //開辟指針的空間
if ( H == NULL )
Error( "out of space" ); //空間開辟失敗
H->Elements = malloc( ( MaxSize + 1 ) * sizeof( T ) ); //把最前邊的作為哨兵
if ( H == NULL )
Error( "out of space" );
//Heap初始化
H->Capacity = MaxSize;
H->Size = 0;
H->Elements[0] = Min; //這個Min是什么大家可以自己定義，比如INT_MIN
return H;
}
這個多一位的“哨兵”有2個好處褒链，一個是左右孩子可以直接取2i和2i+1（不然的話第0位的2倍沒有意義）唁情，第二個是在執(zhí)行元素的插入操作時可以作為結(jié)束循環(huán)的判斷。
那咱們就寫一下如何Insert元素吧甫匹，因?yàn)槎咽怯许樞虻牡槟瘢圆迦霑r必須要考慮如何把它放到合適的位置，一般兵迅，咱們先在堆的末端添加一個空位置抢韭，然后判斷空位置放此元素是不是合理的，不合理的話就把此位置的父節(jié)點(diǎn)下移恍箭，然后嘗試父節(jié)點(diǎn)的位置放置此元素是否合理刻恭，直到根節(jié)點(diǎn)：
template <typename T>
void insert( T x, PriorityQueue H )
{
int i;
if( Queue已經(jīng)滿了 )
{
Error;
return;
}
for( i = ++H->Size; H->Elements[i/2] > x; i /= 2) //i從一個新位置（size+1）開始
//這樣在父節(jié)點(diǎn)的移動時就可以避免繁瑣的swap例程，只用依次放入扯夭；而循環(huán)條件也很簡單鳍贾，
//只要父元素大于它，就把父元素下移交洗，繼續(xù)尋找父元素
H->Elements[i] = H->Elements[i/2];
H->Elements[i] = x;
}
我覺得我已經(jīng)在code里把操作敘述的很清楚了骑科，這里就不再多說，不過只說一點(diǎn)（還是要說肮谷）咆爽，這個循環(huán)條件語句可以用簡單的大小判斷，就是因?yàn)槲覀儼?位置設(shè)為了哨兵（一個很小的值）置森，這樣即使我們需要插入的值是最小值斗埂，當(dāng)它插入到根節(jié)點(diǎn)的位置后，就必然大于0位置的值（1/2=0）凫海，從而結(jié)束循環(huán)蜜笤。
有插入就有刪除，我們實(shí)現(xiàn)一種刪除盐碱，就是刪除最小的元素：堆頂元素把兔。其他的刪除可以參考它：
template<typename T>
T DeleteTop( PriorityQueue H )
{
int i, int child;
T minElement, lastElement;
if( empty( H ) )
{
Error; //空
return H->Elements[0]; //返回第0個元素
}
minElement = H->Elements[1];
lastElement = H->Elements[H->Size--]; //賦給最后一個元素沪伙，同時size減1，因?yàn)橐獎h除一個元素
for( i = 1; i * 2 <= H->Size; i = child)
//條件是(左)兒子在范圍內(nèi)县好，因?yàn)槿绻蠛⒆硬辉谀敲从液⒆颖厝徊辉? {
child = i * 2;
if( child != H->size && H->elements[child + 1] < H->elements[child])
//這里我們沒有明顯檢測右孩子是否存在围橡，但是其實(shí)用了child != H->size來控制，這里的缕贡！=
//其實(shí)就是<翁授，只有它不是最后一位，那么就保證了child+1位置的存在
child++;
if( lastElements>H->elements[child] )
H->elements[i] = H->elements[child];
else
break;
}
H->elements[i] = lastElements;
return minElements;
}
有了這個刪除堆頂（最辛肋洹）元素的例程收擦，我們就可以做刪除任意元素的操作：把想要刪除的元素賦值為最小元素，即給它一個小于堆頂元素的值谍倦，然后Insert到堆頂塞赂，最后執(zhí)行DeleteTop就好了。
我們寫了很多關(guān)于二叉堆的操作昼蛀，其實(shí)和馬上要寫的堆排序代碼并不太一致宴猾，至少不需要掌握復(fù)雜的插入刪除，但它是我們理解堆排序的必要知識叼旋。
現(xiàn)在我們來看堆排序就很簡單了仇哆，它的主要操作就是：
- 拿數(shù)據(jù)建堆。
- 按照規(guī)則刪堆（解散堆）夫植，因?yàn)橹粍h除堆頂?shù)亩锾蓿首詈蟮玫降氖且粋€有序序列。
假設(shè)我們還是需求一個非減序列详民，那么相應(yīng)的延欠，我們最好建一個最大堆，因?yàn)樽畲蠖训膖op delete之后可以放到堆尾阐斜，這樣的排序不需要額外的空間，可以說是相當(dāng)成功了诀紊。
作為一個可以用的排序谒出，我覺得應(yīng)該從數(shù)組的第0位開始（廢話，就這么一個數(shù)組做原地排序邻奠，你不從第0位開始從哪開始绑栽？）碌宴，也因?yàn)槭菑牡?位開始的杀狡，左孩子就不能是2i了（上邊講過），得是2i+1贰镣。那么呜象，我們寫寫膳凝？
#define LeftChild(i) (2*(i)+1)
template<typename T>
void heap( T a[], int i, int n )
{
int child;
T tmp;
for( tmp = a[i]; LeftChild(i) < n; i = child )
{
child = LeftChild(i);
if( child != n - 1 && a[child+1] > a[child] )
child++;
if( tmp < a[child] ) //建立最大堆，那么就是parent小于child時恭陡，child上移
a[i] = a[child];
else
break; //找到了合適的位置蹬音，停止循環(huán)
}
a[i] = tmp;
}
這個建堆的基礎(chǔ)操作，被我們拿來既用作建堆休玩，也用做刪堆著淆，當(dāng)然在這里更好的稱呼是排序：建堆就不用講了，就是從最后一位元素開始逐漸建立小堆拴疤，然后合并成大堆永部；而排序的過程就是把top元素放入堆尾，對其他元素做重建堆：
template<typename T>
void HeapSort( T a[], int n )
{
int i;
for( i = n/2; i >= 0; i-- )
heap( a, i, n ); //建堆
for( i = n - 1; i > 0; i--) //一個微小的點(diǎn)：i>0呐矾，不需要=苔埋，因?yàn)樽詈笠豁?xiàng)不用排序
{
swap( a[0], a[i] ); //交換第0項(xiàng)和最后一項(xiàng)后，排除最后一項(xiàng)建堆
heap( a, 0, i );
}
}
以上2段代碼只有2個需要注意的地方凫佛，一是HeapSort()建堆的過程中讲坎，從i=n/2;開始，而不是很多代碼的i=n-1;愧薛，因?yàn)樽詈笠粚硬]有什么可建的晨炕，完全是浪費(fèi)時間；二是在HeapSort()執(zhí)行heap()時毫炉，最后一個參數(shù)是數(shù)組的數(shù)量瓮栗，也就是數(shù)組的最后一項(xiàng)加1，因?yàn)樵?code>heap()中的循環(huán)條件決定了我們是拿n來比較的瞄勾，這和其他排序的例程中使用n-1稍微有所區(qū)別费奸。
目前，我們已經(jīng)把所有經(jīng)典的排序都過了一遍进陡，順便還講了遞歸式的證明愿阐，以及二叉堆，在一般的算法課上趾疚，這大概需要不到一個月的時間缨历，希望大家喜歡。
