算法描述
堆排序(heapsort)與歸并排序一樣邮破，但不同于插入排序的是，其時間復(fù)雜度為。而與插入排序相同，但不同于歸并排序的是更哄，堆排序同樣具有空間原址性：任何時候只需要常數(shù)個額外的元素空間存儲臨時數(shù)據(jù)。
在堆排序算法中扣草，我們使用的是最大堆佳头。最小堆通常用于構(gòu)造優(yōu)先隊列。
(二叉)堆是一個數(shù)組注竿，它可以被看成一個近似的完全二叉樹茄茁。除了最底層外，該樹是完全充滿的巩割，而且是從左到右填充裙顽。表示堆的數(shù)組A包含兩個屬性：A.length(通常)給出數(shù)組元素的個數(shù)，A.heap-size表示有多少個堆元素存儲在該數(shù)組中宣谈。也就是說愈犹，雖然A[1..A.length]可能都存有數(shù)據(jù)，但只有A[1..A.heap-size]中存放的是堆的有效元素闻丑，這里漩怎，0≤A.heap-size≤A.length。
維護堆的性質(zhì)
MAX-HEAFIFY用于維護最大堆的性質(zhì)梆掸。它的輸入為一個數(shù)組和一個下標i扬卷。在調(diào)用MAX-HEAPIFY的時候，我們假定根節(jié)點為LEFT(i)和RIGHT(i)的二叉樹都是最大堆酸钦，但這是A[i]有可能小于其孩子怪得，這違背了最大堆的性質(zhì)。MAX-HEAPIFY通過讓A[i]的值在最大堆中“逐級下降”卑硫，從而使得以下標i為根節(jié)點的子樹重新遵循最大堆的性質(zhì)徒恋。
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)
時間復(fù)雜度為O(lgn)，即O(h)欢伏。
建堆
可以用自底向上的方法利用過程MAX-HEAPIFY把一個大小為n=A.length的數(shù)組A[1..n]轉(zhuǎn)換為最大堆入挣。子數(shù)組中的元素都是樹的葉子節(jié)點。每個葉節(jié)點都可以看成只包含一個元素的堆硝拧。過程BUILD-MAX-HEAP對樹中的其它節(jié)點都調(diào)用一次MAX-HEAPIFY径筏。
BUILD-MAX-HEAP(A)
A.heap-size = A.length
for i = A.length/2 downto 1
MAX-HEAPIFY(A, i)
時間復(fù)雜度： O(n)葛假。
堆排序算法
初始時，堆排序算法利用BUILD-MAX-HEAP將輸入數(shù)組A[1..n]建成最大堆滋恬，其中n=A.length聊训。因為數(shù)組中的最大元素總在根節(jié)點A[1]中，通過把它與A[n]進行互換恢氯，我們可以讓該元素放到正確的位置带斑。這時，如果我們從堆中去掉節(jié)點n（通過減少A.heap-size的值實現(xiàn)）勋拟，剩余的節(jié)點中勋磕，原來根的孩子節(jié)點仍然是最大堆，而新的根節(jié)點可能會違背最大堆的性質(zhì)敢靡。為了維護最大堆的性質(zhì)挂滓，我們要做的是調(diào)用MAX-HEAPIFY(A, 1)，從而在A[1..n-1]上構(gòu)造一個新的最大堆啸胧。最排序算法會不斷重復(fù)這一過程杂彭，直到堆的大小從n-1降到2。
HEAPSORT(A)
BUILD-MAX-HEAP(A)
for i = A.length downto 2
exchange A[1] with A[i]
A.heap-size = A.heap-size - 1
MAX-HEAPIFY(A, 1)
優(yōu)先級隊列
優(yōu)先級隊列是一種用來維護由一組元素構(gòu)成的集合S的數(shù)據(jù)結(jié)構(gòu)吓揪，其中的每一個元素都有一個相關(guān)的值，稱為關(guān)鍵字所计。一個最大優(yōu)先級隊列支持以下操作:
- INSERT(S, x): 把元素x插入集合S中柠辞。
- MAXIMUM(S): 返回S中具有最大鍵字的元素。
- EXTRACT-MAX(S): 去掉并返回S中具有最大鍵字的元素主胧。
- INCREASE-KEY(S, x, k): 將元素x的關(guān)鍵字值增加到k叭首，這里假設(shè)k的值不小于x的原關(guān)鍵字值。
HEAP-MAXIMUM(A)
return A[1]
時間復(fù)雜度Θ(1)踪栋。
HEAP-EXTRACT-MAX(A)
if A.heap-size < 1
error "heap underflow"
max = A[1]
A[1] = A[A.heap-size]
A.heap-size = A.heap-size - 1
MAX-HEAPIFY(A, 1)
return max
時間復(fù)雜度為O(lgn)焙格。
HEAP-INCREASE-KEY(A, i, key)
if key < A[i]
error "new key is smaller than current key"
A[i] = key
while i > 1 and A[PARENT(i)] < A[i]
exchange A[i] with A[PARENT(i)]
i = PARENT(i)
時間復(fù)雜度為O(lgn).
MAX-HEAP-INSERT(A, key)
A.heap-size = A.heap-size + 1
A[A.heap-size] = -INF
HEAP-INCREASE-KEY(A, A.heap-size, key)
運行時間O(lgn)。
特性：
堆排序為非穩(wěn)定排序
