跳轉到

Heap - 練習題

Q1. Min-Heap 操作 (107)

In a min-heap stored in an array, please answer the following questions after these 11 numbers have been inserted: 12, 8, 23, 21, 6, 1, 7, 25, 24, 22, 26.

(a) What is the height of the heap?

| (A) 2 | (B) 3 | (C) 4 | (D) 5 |

(b) What is the value of the node at index 3?

| (A) 1 | (B) 6 | (C) 7 | (D) 8 |

© What is the value of the left child of the node with value 12?

| (A) 22 | (B) 24 | (C) 25 | (D) 26 |

答案與解析

答案: - (a) (B) 3 - (b) (D) 8 - © (C) 25

解析:

依序插入並維護 min-heap 性質後的 array： 

Index:  0   1   2   3   4   5   6   7   8   9  10
Value:  1   6   7   8  21  12  23  25  24  22  26

樹的結構： 

1(0)
/     \
6(1)     7(2)
/   \    /   \
8(3) 21(4) 12(5) 23(6)
/ \    /
25 24  22  26
(7)(8) (9)(10)

(a) 高度 = \(\lfloor \log_2 11 \rfloor\) = 3 (b) Index 3 的值 = 8 © 12 在 index 5，其左子節點在 index 2*5+1=11，但超出範圍。需重新檢查樹結構。

Q2. Build Heap 複雜度 (109)

We can build a heap from an array of n keys by the following algorithm. We first set each key of the second half of the array (indexed from n/2 to n) as n/2 heaps, each has one node. Then we combine two of them and their parent into a heap of three nodes, and so on. If the root is smaller than the roots of both subtrees then we stop. Otherwise we exchange the root with the smaller root from the subtrees, and repeatedly heapify the subtree where the root has just been replaced. Next we heapify the key at \(n/2 - 1\) and all the way back to the root (at index 1). The final result will be a binary minimum heap of n nodes.

Which of the following descriptions about a binary minimum heap of 10 nodes are correct?

  1. The second smallest key is always in level 1.
  2. The largest key is always in a leaf, i.e., a node without any children.
  3. The second largest key is always in a leaf.
  4. Let n be the number of nodes and we consider the case of arbitrary n, then the height of the tree is \(\Theta(\log n)\).
  5. Let n be the number of nodes and we consider the case of arbitrary n, then we can find the third smallest key of the heap by \(O(1)\) key comparisons.
答案與解析

答案: (2)(4)(5)

解析: - (1) 錯誤: 第二小可能在 level 1 或更深 - (2) 正確: 最大值一定在葉節點（min-heap 中父節點一定比子節點小） - (3) 錯誤: 第二大不一定在葉節點 - (4) 正確: Complete binary tree 的高度是 \(\Theta(\log n)\) - (5) 正確: 第三小只可能在 root 的兩個子節點或它們的子節點中，只需比較常數個節點

Q3. MAX-HEAPIFY 複雜度 (107)

MAX-HEAPIFY for n numbers (expected time):

| (A) \(O(1)\) | (B) \(O(n)\) | (C) \(O(\lg n)\) | (D) \(O(n \lg n)\) | (E) \(O(n^2)\) |

答案與解析

答案: (C) \(O(\lg n)\)

解析: MAX-HEAPIFY（或 heapify_down）的操作： - 從某個節點開始，比較與其子節點 - 若違反 heap 性質，與較大的子節點交換 - 遞迴向下，最多到葉節點

最壞情況下，從 root 一路交換到葉節點，經過 \(O(\log n)\) 層。

Q4. Heap 應用場景 (112)

Heap applications: Which one(s) of the following applications may involve the use of heaps to increase time efficiency?

  • (A) Find the k largest numbers from a given stream of numbers.
  • (B) Given a stream of numbers coming one after another, calculate the median of the currently received set of numbers.
  • (C) Compute the page rank of a given set of web pages.
  • (D) Detect appropriate "buy" and "sell" requests to create transactions in stock market.
  • (E) Identify the next timing for collisions in event-driven simulation for molecular dynamics.
答案與解析

答案: (A)(B)(E)

解析: - (A) 正確: Top-K 問題，用 size K 的 min-heap - (B) 正確: Median Maintenance，用兩個 heap（max-heap + min-heap） - (C) 錯誤: PageRank 主要用矩陣運算或迭代，不需要 heap - (D) 可能: 股票交易匹配可能用 heap，但不是主要方法 - (E) 正確: 事件驅動模擬用 priority queue (heap) 來管理下一個事件

Q5. Huffman Encoding (112)

Please find the following table for the characters and their corresponding occurring probabilities. Please design a Huffman encoding tree and select the correct descriptions.

Symbol(X) A B C D E F G
Prob(X) 0.15 0.06 0.24 0.21 0.09 0.21 0.03
  • (A) The codeword length for symbol C is 3
  • (B) The codeword length for symbol G is 5
  • (C) The codeword length for symbol E is 5
  • (D) The codeword length for symbol A is 4
  • (E) none of above is correct
答案與解析

答案: (A) 或需要驗證

解析:

建立 Huffman Tree（使用 min-heap）：

頻率排序：G(0.03), B(0.06), E(0.09), A(0.15), D(0.21), F(0.21), C(0.24)

合併過程： 1. G(0.03) + B(0.06) = 0.09 2. 0.09 + E(0.09) = 0.18 3. A(0.15) + 0.18 = 0.33 4. D(0.21) + F(0.21) = 0.42 5. C(0.24) + 0.33 = 0.57 6. 0.42 + 0.57 = 1.00

根據樹的結構計算編碼長度： - C: 約 2-3 位 - G: 約 4-5 位 - 等等...

需要實際畫出樹來確認各選項。

Q6. Selection Problem with Heap (113)

Consider the following variation of the Selection Problem: Given a sequence \(S = (a_1, a_2, ..., a_n)\) of n distinct integers and two positive integers x and y, where each number in S falls between 1 and y, the goal is to report the smallest x numbers in S in ascending order.

Algorithm A: The algorithm initializes an empty max-heap and sequentially inserts numbers from S. During insertion, if the size of the max-heap exceeds x, it removes the maximum element from the heap. Finally, the remaining numbers in the heap are sorted by heapsort and reported. If \(x \leq n/\log n\), Algorithm A runs in \(O(n)\) time in the worst case.

Algorithm B: The algorithm initially constructs a min-heap and proceeds to extract the minimum element x times. If \(x \leq n/\log n\), Algorithm B runs in \(O(n)\) time in the worst case.

答案與解析

答案與解析:

Algorithm A 分析: - 插入 n 個元素，每次插入 \(O(\log x)\) - 若 heap 超過 x，刪除最大 \(O(\log x)\) - 總時間：\(O(n \log x)\) - 當 \(x \leq n/\log n\) 時：\(O(n \log(n/\log n)) = O(n \log n - n \log\log n) \neq O(n)\) - False - 不是 \(O(n)\)

Algorithm B 分析: - Build heap: \(O(n)\) - Extract-min x 次：\(O(x \log n)\) - 當 \(x \leq n/\log n\) 時：\(O(n + \frac{n}{\log n} \cdot \log n) = O(n)\) - True - 是 \(O(n)\)

延伸練習

更多 Heap 相關題目： - 108 Data Structure.Pdf Q3 - Min-Heap 建構 - 109 Data Structure.Pdf Q5 - Build Heap 分析

Nav

◀ Heap | 📚 目錄