堆排序（HeapSort）
(2008-07-30 10:43:52)
- 堆的介紹：堆是一種數(shù)組，但是以樹的結(jié)構(gòu)形式來看待它，如下標(biāo) i 節(jié)點(diǎn)的求解Parent和Children節(jié)點(diǎn)如下：
PARENT(i)
return ?i/2?
LEFT(i)
return 2i
RIGHT(i)
return 2i + 1
堆分為MAX-堆和MIN-堆，
MAX堆滿足的條件為： A[PARENT(i)] ≥ A[i] ,
MIN堆滿足的條件為： A[PARENT(i)] ≤ A[i] .
- MAX和MIN堆的維持：
這里只對(duì)MAX堆，MIN對(duì)類似：數(shù)組A的LEFT(i) 和
RIGHT(i) 都是MAX堆，但可能A[ i
]可能小于它的Children節(jié)點(diǎn)，所以需要調(diào)整，調(diào)整偽代碼如下：
MAX-HEAPIFY(A, i)
1 l ← LEFT(i)
2 r ← RIGHT(i)
3 if l ≤ heap-size[A] and A[l] > A[i]
4 then largest ← l
5 else largest ← i
6 if r ≤ heap-size[A] and A[r] > A[largest]
7 then largest ← r
8 if largest ≠ i
9 then exchange A[i] ? A[largest]
10 MAX-HEAPIFY(A, largest)
-
MAX堆建立：
BUILD-MAX-HEAP(A)
1 heap-size[A] ← length[A]
2 for i ← ?length[A]/2? downto 1
3 do MAX-HEAPIFY(A, i)
如下面建立MAX過程：
-
4 堆排序(HeapSort)
首先是把一個(gè)給定的數(shù)組變成MAX堆，然后把根節(jié)點(diǎn)和堆的最后一個(gè)交換，堆的大小減1，再調(diào)整堆，
這樣下去，直到堆的大小為1：
偽代碼如下：
HEAPSORT(A)
1 BUILD-MAX-HEAP(A)
2 for i ← length[A] downto 2
3 do exchange A[1] ? A[i]
4 heap-size[A] ← heap-size[A] - 1
5 MAX-HEAPIFY(A, 1)
堆排序的圖解過程如下：
|
