樣式表運作中

回到目錄

6 Heap Sort

• 6 Heap Sort
  • • 習題
  • 6.2 維持堆積特性
    • 習題
  • 6.3 建構堆積
  • 6.4 堆積排序演算法
  • 6.5 優先佇列
    • implement

(二元)堆積可以被視為 nearly complete binary tree

complete binary tree

各層節點全滿，除了最後一層，最後一層節點全部靠左。

一顆二元樹需要滿足 heap-property 才能被稱為堆積。

• max heap 要滿足 max-heap property：
  $A[PARENT(i)]\le A[i]$
• min heap 要滿足 min-heap property：
  $A[PARENT(i)]\ge A[i]$

堆積樹節點的 height，是從該節點到 leaf node 的最長簡單路徑的邊數。一個有

$n$ 個元素的 heap 高度

$h=\mathrm{\Theta }(\lg n)$。

heap 的基本操作：

• MAX-HEAPIFY：
  $O(\lg n)$
• BUILD-MAX-HEAP：
  $O(n)$
• HEAPSORT：
  $O(n\lg n)$
• priority queue
  • MAX-HEAP-INSERT
  • MAX-HEAP-EXTRACT-MAX
  • MAX-HEAP-INCREASE-KEY
  • MAX-HEAP-MAXIMUM

習題

6.1-1

在高度為

$h$ 的堆積中的元素數量，最少有幾個元素？最多有幾個元素？

最多會有

$\sum _{i=0}^k{2}^i$ 個元素，最少會有

$(\sum _{i=0}^{k-1}{2}^i)+1$。

$$\begin{array}{rl}\sum _{i=0}^n{2}^i=& 2^0+2^1+2^2\dots +2^n\\ =& (1{)}_2+(10{)}_2+(100{)}_2+\dots +(100\dots 0{)}_2=(111\dots 11{)}_2\\ ◼& =& 2^{n+1}-1\end{array}$$

所以高度為

$h$ 的二元堆積樹中，最少會有

$2^h$ 個節點，最多會有

$2^{h+1}-1$

6.1-2

證明包含

$n$ 個元素的堆積的高度是

$\lfloor \lg n\rfloor$

由上一題證明得出高度為

$h$ 的二元堆積樹至少需要

$2^h$ 個元素最多需要

$2^{h+1}-1$。對兩數字取

$\lg$ 可以得到

$h$ 與很接近

$h+1$ 的數字，因此如果一個二元堆積樹有

$n$ 個元素，其高為

$\lfloor \lg n\rfloor$。

6.1-3

證明最大堆積的任何子樹的根的值，比那顆子樹的任何其他值都要大。

max heap 需要滿足 max-heap property，也就是每一個非根節點的值會小於等於父節點的值。因此對於每一個子樹，其根節點的子節點的值皆會小於根節點的值，其他節點也滿足 max-heap property。

6.1-4

最大堆積中，最小的元素可能在哪裡？假設所有元素都不同。

由於 max-heap 會滿足 max-heap properity，因此最小的值會在高度 h 的 leaf node 之中。

6.1-5

在最大堆積裡，第

$k$ 大的元素可能在哪一層？設

$2\le k\le \lfloor n/2\rfloor$，且所有元素都不一樣。

• 第
  $1$ 大會在第
  $0$ 層
• 第
  $2\to 3$ 大會在第
  $1$ 層
• 第
  $4\to 7$ 大會在第
  $2$ 層
• 第
  $2^n\to 2^n-1$ 會在第
  $n$ 層

假設

$2^x\le k\le 2^{x+1}-1$，同時取

$\lg$ 會是

$x\le \lg k<x+1$。
所以第

$k$ 大的元素會在第

$\lfloor \lg n\rfloor$ 層。

6.1-6

已排序的陣列是最小堆積嗎？

是

6.1-7

值為

$⟨33,19,20,15,13,10,2,13,16,12⟩$ 的陣列會是最大堆積嗎？

6.1-8

證明：在

$n$ 個元素的堆積的陣列表示法中，葉節點的索引是

$\lfloor n/2\rfloor +1,\lfloor n/2\rfloor +1,\dots ,n$。

葉節點會在二元堆積數的最後一層，假設樹有

$h$ 層，第一個葉節點會從

$2^h$ 開始，會在

$2^{h+1}-1$ 結束。

6.2 維持堆積特性

MAX-HEAPIFY 會使 root node 索引為 i 的子樹符合 max-heap properity 。

BUILD-MAX-HEAP(A, n)
1L = LEFT(i)
2R = RIGHT(i)
3if l ≤ A.heap-size and A[r] > A[i]
4    largest = l
5else largest = i
6if r ≤ A.heap-size and A[r] > A[largest]
7   largset = r
8if largset ≠ i
9    exchange A[i] with A[largest]
10    MAX-HEAPIFY(A, largst)

i 節點的子樹大小不超過 2n/3

$T(n)\le T(2n/3)+\mathrm{\Theta }(1)$

習題

6.2-1

6.2-2

6.2-3

6.2-4

6.2-5

6.2-6

6.2-7

6.3 建構堆積

$A[\lfloor n/2\rfloor +1:n]$ 都是 leaf node，

BUILD-MAX-HEAP(A, n)
1A.heap-size = n
2for i = floor(n/2) down to 1
3    MAX-HEAPIFY(A, i)

6.4 堆積排序演算法

HEAPSORT(A, n)
1for i = n down to 2
2    swap(A[l], A[i])
3    A.heap-size = A.heap-size - 1
4    MAX-HEAPIFY(A, 1)

+---+---+---+---+---+---+---+---+---+
|      heap     |    sorted array   |
+---+---+---+---+---+---+---+---+---+

6.5 優先佇列

implement

#define PARENT(i)   i/2
#define LEFT(i)     i*2
#define RIGHT(i)    i*2+1

#define SWAP(a, b) (a ^= b, b = a ^ b, a ^= b)

// start heapify form node A[i]
void max_heapify(int *A, int n, int i) {
    int l = LEFT(i);
    int r = RIGHT(i);
    int max;
    
    // root node must larger than left and right
    if(l < n && A[l] > A[i]) {
        max = l;
    } else max = i;
    
    if(r < n && A[r] > A[max]) {
        max = r;
    }
    
    if(max != i){
        SWAP(A[max], A[i]);
        max_heapify(A, max);
    }
}

void build_max_heap(int *A, int n) {
    for(int i = n / 2; i >= 1; i--) {
        max_heapify(A, n, i);
    }    
}