算法導論之堆排序相關

堆排序文檔 二叉堆分為兩種：最大堆、最小堆

最大堆：最大元素在根部，在堆的所有結點中，A[PATENT(i)]>=A[i]

最小堆：最小元素在根部，在堆的所有結點中，A[PATENT(i)]<=A[i]

下面以最大堆為例解釋堆排序的具體過程：

首先會用到幾個基本的函數：

PARENT(i)

Return ⌊i/2⌋

LEFT(i)

Return 2i

RIGHT(i)

Return 2i+1

這是三個基本函數，分别求的是二叉堆中第i個元素的父節點，左孩子結點和右孩子結點的标号

函數MAX-HEAPFY(A,i)是用來維護最大堆的基本性質，即就是（最大元素在根部，在堆的所有結點中，A[PATENT(i)]>=A[i]），函數的實作原理就是比較結點i的本身的值和此結點的左右子樹的結點的值，将最大的值賦給結點i，即雙親結點。若是發生了變化，即就是原本最大的并不是根節點，後來進行了變換才将最大的值賦給了根節點，此時就要繼續進行此操作，一直往下處理，直到不再發生變換時結束。函數MAX-HEAPFY(A,i)中，A代表的是存放資料的數組，i表示的要處理的結點的序号。

函數MAX-HEAPFY(A,i)的僞代碼如下：

MAX-HEAPFY(A,i):

l=LEFT(i);

r=RIGHT(i);

if l<=A.heap-size && A[l]>A[i]

largest=l;

else largest=i;

if r<=A.heap-size && A[r]>A[largest]

largest=r;

if largest!=i

exchange A[i] with A[largest]

MAX-HEAPFY(A,largest)

其中，A.heap-size指的是數組A的有效的元素的個數（此函數的作用是，在一個元素的排列順序滿足堆的性質的數組中，變換了其中一個元素的位置，使得數組不再滿足堆的性質的條件時，進行調整，使數組重新變得有序）

上面地函數MAX-HEAPFY(A,i)相當于建立了一個優先隊列，下面要進行建堆：

用函數BUILD-MAX-HEAP(A)來實施建堆，此函數的本質是不斷地調用函數MAX-HEAPFY(A,i)，

對調換了第一個和最後一個元素的數組中元素的位置進行重新整理，使得元素之間滿足堆的結構（注意堆的結構并不是按照從大到小的順序從前到後進行排列）。

函數BUILD-MAX-HEAP(A)的僞代碼如下：

BUILD-MAX-HEAP(A):

A.heap-size=A.length;

for i=⌊A.length/2⌋ downto 1

MAX-HEAPFY(A,i);

此函數執行完畢，存放原始資料的數組裡的元素就按照最大堆的順序排列好了，現在可以開始進行堆排序了

堆排序算法：基于前面的基礎工作之上，堆排序算法的實作就變得很簡單了，即就是首先建堆，然後将第一個元素和最後一個元素的位置互換，就得到了第一個元素，将它從原來的數組中單獨拿出來，接着調用函數MAX-HEAPFY(A,i)來使堆維持其特性，再互換第一個元素和最後一個元素，就又可以得到一個新的元素，一直執行此操作，直到拿到了所有的元素。

堆排序算法的僞代碼如下：

HEAPSORT(A):

BUILE-MAX-HEAP(A)

for i=A.length downto 2

exchange A[1] with A[i]

A.heap-size=A.heap-size-1;

MAX-HEAPFY(A,1)

堆排序算法HEAPSORT(A)的時間複雜度為O(nlgn)，（性能最差的排序算法，例如冒泡和選擇排序，他們的時間複雜度都是O(n*n)）

由于快排的性能一般要優于堆排序，是以，與快排相比較，堆排序更大的用處展現在優先隊列上。包含最大優先隊列和最小優先隊列。最大優先隊列經常用于類似于作業系統中的共享計算機系統的作業排程；而最小優先隊列經常用于基于事件驅動的模拟器。