演算法導論—6 Heapsort

--- title: 演算法導論—6 Heapsort tags: - 演算法導論 - 筆記 ---  {%hackmd SyahHjQRC %} [回到目錄](https://hackmd.io/@yuto0226/SJyYUFXAC/%2FSJyYUFXAC) # 6 Heap Sort [toc] (二元)堆積可以被視為 nearly complete binary tree > [!Note] 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 = \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** :::info 在高度為 $h$ 的堆積中的元素數量，最少有幾個元素？最多有幾個元素？ ::: 最多會有 $\sum_{i=0}^k 2^i$ 個元素，最少會有 $(\sum_{i=0}^{k-1} 2^i)+1$。 $$ \begin{align} \sum_{i=0}^n 2^i=&2^0+2^1+2^2\ldots+2^n \\ =&(1)_2+(10)_2+(100)_2+\ldots+(100 \ldots 0)_2=(111 \ldots 11)_2\\ =& 2^{n+1}-1 \tag*{$\blacksquare$} \end{align} $$ 所以高度為 $h$ 的二元堆積樹中，最少會有 $2^h$ 個節點，最多會有$2^{h+1}-1$ **6.1-2** :::info 證明包含 $n$ 個元素的堆積的高度是 $\lfloor \lg n \rfloor$ ::: 由上一題證明得出高度為 $h$ 的二元堆積樹至少需要 $2^h$ 個元素最多需要 $2^{h+1} - 1$。對兩數字取 $\lg$ 可以得到 $h$ 與很接近 $h+1$ 的數字，因此如果一個二元堆積樹有 $n$ 個元素，其高為 $\lfloor \lg n \rfloor$。 **6.1-3** :::info 證明最大堆積的任何子樹的根的值，比那顆子樹的任何其他值都要大。 ::: max heap 需要滿足 max-heap property，也就是每一個非根節點的值會小於等於父節點的值。因此對於每一個子樹，其根節點的子節點的值皆會小於根節點的值，其他節點也滿足 max-heap property。 **6.1-4** :::info 最大堆積中，最小的元素可能在哪裡？假設所有元素都不同。 ::: 由於 max-heap 會滿足 max-heap properity，因此最小的值會在高度 h 的 leaf node 之中。 **6.1-5** :::info 在最大堆積裡，第 $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** :::info 已排序的陣列是最小堆積嗎？ ::: 是 **6.1-7** :::info 值為 $\langle 33, 19, 20, 15, 13, 10, 2, 13, 16, 12 \rangle$ 的陣列會是最大堆積嗎？ ::: ![IMG_0384](https://hackmd.io/_uploads/BJ1bhC1xkg.jpg) **6.1-8** :::info 證明：在 $n$ 個元素的堆積的陣列表示法中，葉節點的索引是 $\lfloor n/2 \rfloor + 1, \lfloor n/2 \rfloor + 1, \ldots, n$。 ::: 葉節點會在二元堆積數的最後一層，假設樹有 $h$ 層，第一個葉節點會從 $2^h$ 開始，會在 $2^{h+1}-1$ 結束。 ## 6.2 維持堆積特性 MAX-HEAPIFY 會使 root node 索引為 i 的子樹符合 max-heap properity 。 <pre class="part" id="pseudocode"> 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) </pre> ![image](https://hackmd.io/_uploads/B14t4Hkgkx.png) i 節點的子樹大小不超過 2n/3 $T(n) \le T(2n/3) + \Theta(1)$ ### 習題 **6.2-1** :::info ::: **6.2-2** :::info ::: **6.2-3** :::info ::: **6.2-4** :::info ::: **6.2-5** :::info ::: **6.2-6** :::info ::: **6.2-7** :::info ::: ## 6.3 建構堆積 $A[\lfloor n/2 \rfloor + 1:n]$ 都是 leaf node， <pre class="part" id="pseudocode"> BUILD-MAX-HEAP(A, n) 1A.heap-size = n 2for i = floor(n/2) down to 1 3 MAX-HEAPIFY(A, i) </pre> ## 6.4 堆積排序演算法 <pre class="part" id="pseudocode"> 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) </pre> ``` +---+---+---+---+---+---+---+---+---+ | heap | sorted array | +---+---+---+---+---+---+---+---+---+ ``` ## 6.5 優先佇列 ### implement ```c #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); } } ```