資料結構累堆排序法

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

請大家幫我解答一下

謝謝喔!!

1 Answer

Rating
  • 1 decade ago
    Favorite Answer

    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
Still have questions? Get your answers by asking now.