（二叉）堆數(shù)據(jù)結(jié)構(gòu)是一種數(shù)組對象擂仍，是一個完全的二叉樹
二叉堆有兩種：最大堆和最小堆
二叉樹的層次遍歷結(jié)果與數(shù)組元素的順序?qū)?yīng)，樹根為A[1]笑跛。對于數(shù)組中第i個元素
PARENT(i)
return i/2
LEFT(i)
return 2i
RIGHT(i)
return 2i+1
涉及過程：
MAX-HEAPIFY過程位岔，運(yùn)行時間為O(lgN),加入A[i]小于其子節(jié)點如筛，MAX-HEAPIFY會使A[i]下降，子節(jié)點上升抒抬，是保持最大堆性質(zhì)的關(guān)鍵
BUILD-MAX-HEAP過程杨刨，以線性時間運(yùn)行，在無序的輸入數(shù)組基礎(chǔ)上構(gòu)造出最大堆
HEAPSORT過程擦剑，運(yùn)行時間為O(nlgN),對一個數(shù)組原地進(jìn)行排序
保持堆的性質(zhì)
時間復(fù)雜度為：T(n) <= T(2/3n)+O(1)
偽代碼：
MAX-HEAPIFY(A,i)：
l<- LEFT(i)
r<- RIGHT(i)
//----在節(jié)點和左右子節(jié)點中得到最大數(shù)妖胀，heap-size[A]代表存放在數(shù)組A的堆長度
if l<=heap-size[A] and A[l] > A[i]
then largest <- l
else largest <- i
if r<=heap-size[A] and A[r] > A[largest]
then largest <- r
//----
//當(dāng)前節(jié)點小于子節(jié)點就下降，并遞歸直到正確位置
if largest != i
then exchange A[i]<- A[largest]
MAX-HEAPIFY(A,largest)
建堆
建立最大堆的過程是自底向上地調(diào)用最大堆調(diào)整程序?qū)⒁粋€數(shù)組A[1.....N]變成一個最大堆惠勒。將數(shù)組視為一顆完全二叉樹赚抡，從其最后一個非葉子節(jié)點（n/2）開始調(diào)整。調(diào)整過程如下圖所示：
時間復(fù)雜度為 O(n)
偽代碼：
BUILD-MAX-HEAP(A)：
heap-size[A] <- length[A]
for i<-length[A]/2 downto 1 (直到i=1結(jié)束纠屋，包括1)
MAX-HEAPIFY(A,i)
堆排序算法
堆排序算法過程為：先調(diào)用創(chuàng)建堆函數(shù)(BUILD-MAX-HEAP)將輸入數(shù)組A[1...n]造成一個最大堆涂臣，使得最大的值存放在數(shù)組第一個位置A[1]钧椰，然后用數(shù)組最后一個位置元素與第一個位置進(jìn)行交換流炕，并將堆的大小減少1，并調(diào)用最大堆調(diào)整函數(shù)從第一個位置調(diào)整最大堆栅受。給出堆數(shù)組A={4,1,3,16,9,10,14,8,7}進(jìn)行堆排序簡單的過程如下：
時間復(fù)雜度為O(nlogn)
（1）創(chuàng)建最大堆族铆，數(shù)組第一個元素最大岩四，執(zhí)行后結(jié)果下圖：
（2）進(jìn)行循環(huán)，從length(a)到2哥攘，并不斷的調(diào)整最大堆剖煌，給出一個簡單過程如下：
偽代碼：
HEAPSORT(A)：
BUILD-MAX-HEAP(A)
for i<-length[A] downto 2
do exchange A[1] <- A[i]
heap-size[A] <- heap-size[A] - 1
MAX-HEAPIFY(A,1)
鏈接
http://www.cnblogs.com/Anker/archive/2013/01/23/2873422.html
