資料結構›Ch7 搜尋與排序第 38 題/共 76 題
38. Min Heap、Build Heap、Bottom-Up
#DS-07-038易Min HeapBuild HeapBottom-Up
四、非選擇題(共26分):請詳讀下列說明。
Answer the following questions. If you do not know the answer, you have the option to answer "PASS"; in this case, you will receive exact ONE point for that question. Other irrelevant answers to the question make you lose the option. Make good use of the option to maximize your score.
- 4% A binary min-heap (the one for heap-sort) is stored in an array. In a C array, we store values starting from index 1. The array in the above is not a min-heap. Build the min-heap from the array shown above using the bottom-up linear-time algorithm. Present your result in the same array where each value is in the correct array entry.
| index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| val | - | 11 | 5 | 10 | 2 | 9 | 3 | 8 | 4 | 7 | 6 | 1 |
📄 交大115
▤完整推導請見《WH 資工筆記 · 資料結構》Ch7 搜尋與排序