# 算法學習筆記之二（堆排序） 堆其實是一個數組，它可以看成一個二叉樹，用來儲存數組里的元素。  其中10為根結點,25，30，70為葉結點，其余稱為結點。當父結點的鍵值總是大于或等于任何一個子節點的鍵值時為最大堆。當父結點的鍵值總是小于或等于任何一個子節點的鍵值時為最小堆。一個結點的高度就是從結點到葉節點的最長路徑，一個堆的高度就是根節點的高度。含n個元素的堆高度是floor[log2(n)]. 堆排序利用的是最大堆的性質。 ~~~ Parent(i)//返回一個結點的父結點 returnfloor[i/2] Left(i)//返回一個結點的左子節點 return 2*i Right(i) //返回一個結點的右子節點 return 2*i+1 Max_Heapify(i)//維護以i為結點的子樹的最大堆性質 l=Left(i) r=Right(i) if l<=A.heap-size and A[l]>A[i] large=l else large=i if r<= A.heap-size and A[r]>A[larget] larget=r if larget !=i exchanceA[i] with A[larget] Maax_Heapify(A.larget) Build_Max_Heapify(A)//建立一個堆 A.heap-size=A.length For i=floor[A.length/2] downto 2 Max_Heapify(A,i) HeapSort(A)//每一次提取根節點的值，也就是最大值，然后重新建立最大堆 Build_Max_Heapify(A) for i=A.length downto 2 ExchanceA[1] with A[i] A. heap-size =A.heap-size-1 Max_Heapify(A,1) ~~~ 堆排序的時間復雜度也是O（n*log2(n)） 雖然堆排序不是最優，但是其堆的結構卻很能引發我們的思考，比如用堆結構可以實現優先隊列；接下來就是學習優先隊列了。