資料結構累堆排序法

Construct a max-heap with the data sequence: 3, 6, 2, 5, 4, 1, 8, 7

(a) Illustrate the max-heap explicitly at each pass (or step) of sorting process

(b) Find the time complexity of the heap sort

Rating

PARENT(i)

return |_ i / 2 _|

LEFT(i)

return 2i

RIGHT(i)

return 2i+1

--------------------------------------

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)

--------------------------------------------------

BUILD-MAX-HEAP(A)

1heap-size[A] ← length[A]

2for i ← |_ length[A] / 2 _| downto 1

3do MAX-HEAPIFY(A, i)

========================================

(以上為定義)

本題中:

(a)得知heap-size[A] = 8，從8/2 = 4，

依序對(A, 4), (A, 3), (A, 2), (A, 1)

一個一個做MAX-HEAPIFY()

如下圖(先將陣列畫成heap):

3

62

5418

7

MAX-HEAPIFY(A, 4)------(對5做)

3

62

7418

5

MAX-HEAPIFY(A, 3)------(對2做)

3

68

7412

5

MAX-HEAPIFY(A, 2)------(對6做)

3

78

6412

5

MAX-HEAPIFY(A, 1)------(對3做)

8

73

6412

5

上圖即為BUILD-MAX-HEAP(A)的結果

(b)

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)

HEAPSORT的做法是在BUILD-MAX-HEAP完成後，因為MAX-HEAP成立，故 root 必為最大值。則每次都拿第一個數與最後一個數交換，交換後便將陣列長度減1(即將排好的部分踢出heap)，此時最大值必保持在陣列的最後方。接著對 root 做MAX-HEAPIFY，則整個heap(除了踢出的部分)仍為一個MAX-HEAP

在HEAPSORT中:

BUILD-MAX-HEAP 的 time complexity為O(n)

//這部分比較困難我不多做回答

for loop迴圈顯而易見的跑了n-1次

而MAX-HEAPIFY的time complexity為O(lg n)

故HEAPSORT的time complexity為O(n lg n)

Source(s): introduction to ALGORITHMS 2nd edition