二叉樹
二叉樹是一個(gè)特殊結(jié)構(gòu)的樹较木。其特征為根結(jié)點(diǎn)必須有兩個(gè)子節(jié)點(diǎn)侵状，更加嚴(yán)格的遞歸定義是：二叉樹要么為空牺勾；要么由根結(jié)點(diǎn)正罢、左子樹和右子樹組成。
二叉樹中有兩種特殊結(jié)構(gòu)的二叉樹“滿二叉樹”和“完全二叉樹”驻民。
“滿二叉樹”：如果二叉樹的兩個(gè)內(nèi)部結(jié)點(diǎn)又都有兩個(gè)子結(jié)點(diǎn)翻具。定義深度為h的二叉樹且有2的h次方-1個(gè)結(jié)點(diǎn)。
“完全二叉樹”：如果二叉樹的左子樹的子結(jié)點(diǎn)是滿的回还，而右子樹的子結(jié)點(diǎn)缺失一個(gè)或者幾點(diǎn)子結(jié)點(diǎn)裆泳。
“堆”是一種特殊的“完全二叉樹”
“最小堆”：即所有的父結(jié)點(diǎn)都比子結(jié)點(diǎn)要小，堆頂(根結(jié)點(diǎn)）1號(hào)結(jié)點(diǎn)比所有結(jié)點(diǎn)都小柠硕。
（log）對(duì)數(shù)：計(jì)算以2為底的對(duì)數(shù)時(shí)：log2（6） = log6/log2
建立一個(gè)堆
/*建立一個(gè)堆晾虑，首先將這n個(gè)結(jié)點(diǎn)自上到下、自左到右進(jìn)行1到n的編序仅叫，將堆轉(zhuǎn)換成完全二叉樹帜篇，緊接著從最后一個(gè)非葉結(jié)點(diǎn)（編號(hào)為n/2）開始到根結(jié)點(diǎn)（編號(hào)為1），逐個(gè)掃描所有的結(jié)點(diǎn)诫咱，根據(jù)需要將當(dāng)前結(jié)點(diǎn)向下調(diào)整笙隙，直到符合特性。*/
for(i = n/2; i >= 1; i--)
siftdown(i);
堆排序
從小到大排序坎缭，建立最大堆竟痰。
建立好最大堆，最大元素在堆頂(h[1]),因?yàn)槲覀兊男枨笫菑男〉酱笈判蛱秃簦Ｍ畲蟮姆旁谧詈蠡悼欤虼藢[1]和h[n]進(jìn)行交換，此時(shí)h[n]就是最大的元素憎夷，請(qǐng)注意莽鸿，交換后還需將h[1]向下調(diào)整以保持堆的特性。
void heapsort()
{
while(n > 1)
{
swap(1, n);
n--;
siftdown;
}
return;
}
