第二部分 排序和順序統計量
第6章 堆排序
- 複雜度O(nlgn)
- 原址排序
- 集插入排序和歸并排序兩者的優點
1. 堆
- 堆是一個數組，可看成一個近似的完全二叉樹
- 除了最底層外，該樹是完全充滿的
- 從左向右填充
- 堆的高度 = 根結點的高度
-
堆結構上一些基本操作的運作時間至多與樹的高度成正比，即時間複雜度為O(lgn)
表示堆的數組A包括兩個屬性
- A.length給出數組中元素的個數
- A.heap-size表示有多少個堆元素存儲在該數組中
計算給定節點下标i的父，左孩子，右孩子的下标
Parent(i) return i/2
Left(i) return 2i
Right(i) return 2i + 1
最大堆（堆中最大元素存放在根結點）
- A[Parent(i)] >= A[i]
最小堆（堆中最小元素存放在根結點）
- A[Parent(i)] <= A[i]
- 通過用過構造優先隊列
2. 維護堆的性質
從A[i]、A[Left(i)]和A[Right(i)]中選出最大的，并将下标存儲在largest中。如果A[i]是最大的，程式結束。否則，最大元素是i的某個孩子結點，則交換A[i]和A[largest]的值，進而使i及其孩子都滿足最大堆的性質。在交換後，下标為largest的結點的值是原來的A[i]，于是以該結點為根的子樹又可能會違反最大堆的性質，是以，需要對孩子樹遞歸調用Max-heapify
Max-Heapify(A, i)
l = Left(i)
r = Right(i)
if l <= A.heap-size and A[l] > A[i]
largest = l
else
largest = i
if r <= A.heap-size and A[r] > A[largest]
largest = r
if largest != i
exchange A[i] with A[largest]
Max-Heapify(A, largest)
Max-heapify的時間複雜度為O(h)， h = 樹高。
當用數組存儲n個元素的堆時，葉結點下标分别是⌊n/2⌋+1, ⌊n/2⌋+2, …, n.
3. 建堆
用自底向上的方法利用過程Max-heapify把一個大小為n = A.length的數組A[1..n]轉換為最大堆。
Build-Max-Heap(A)
A.heap-size = A.length
for i = ⌊A.length/⌋ downto
Max-Heapify(A, i)
每次調用Max-Heapify的時間複雜度是O(lgn)，Build-Max-Heap需要O(n)次這樣的調用。是以總的時間複雜度是O(nlgn)。這個上界雖然正确，但不是漸近緊确。
4. 堆排序
先建成最大堆，因數組中最大的元素在根結點A[1]，通過把它與A[n]互換，可以儲存最大的元素并從堆中去掉結點n，剩餘的結點中，原來根的孩子結點仍然是最大堆，而新的根結點可能會違背最大堆的性質，是以需要調用Max-Heapify(A, 1)構造一個新的最大堆，不斷重複這一過程，直到堆的大小降到2。
Heapsort(A)
Build-Max-Heap(A)
for i = A.length downto
exchange A[] with A[i]
A.heap-size = A.heap-size -
Max-Heapify(A, )
時間複雜度O(nlgn)
5. 優先隊列（用堆實作）
優先隊列有兩種形式
1. 最大優先隊列
2. 最小優先隊列，可被用于基于事件驅動的模拟器。隊列中儲存要模拟的事件，每個事件都有一個發生時間作為其關鍵字。事件必須按照發生的時間順序進行模拟，因為某一事件的模拟結果可能會觸發對其他事件的模拟
Heap-Maximum(A)
return A[]
Heap-Extract-Max(A)
if A.heap-size <
error "heap underflow"
max = A[]
A[] = A[A.heap-size]
Max-Heapify(A, )
return max
修改關鍵字的大小後，目前元素會不斷地與其父結點進行比較，如果目前元素的關鍵字較大，則目前元素與其父結點進行交換。不斷重複該過程，直到目前元素的關鍵字小于其父結點時終止。
Heap-Increase-Key(A, i, key)
if key < A[i]
error "new key is smaller than currenty key"
A[i] = key
while i > and A[Parent(i)] < A[i]
exchange A[i] with A[Parent(i)]
i = Parent(i)
首先增加一個葉結點來擴充最大堆，然後調用Heap-Increase-Key為新結點設定對應的關鍵字，同時儲存最大堆的性質
Max-Heap-Insert(A, key)
A.heap-size = A.heap-size +
A[A.heap-size] =
Heap-Increase-Key(A, A.heap-size, key)