我最近參加了計算機科學考試，有一個類似的問題。
有兩個最大堆（實作了陣列）。你需要想出一個演算法來合并這兩個最大堆并創建一個新的最大堆（陣列實作）
問題的解法很直觀就是：
- 合并兩個陣列
- 呼叫堆重建
我查看了互聯網并遇到了相同型別的解決方案。
但是，我寫了一個我自己無法反駁的解決方案。
我的演算法
- 創建 index1 和 index2 指向 heapArr1 和 heapArr2 的第一個元素
- 創建一個大小為 heapArr1.size heapArr2.size 的新堆陣列
- 在while回圈中
- 比較 heapArr1 的 index1 元素和 heapArr2 的 index2 元素
- 以較大者為準，寫入結果陣列并增加該元素所采用的陣列的索引，直到兩個陣列都被遍歷。
例如
堆 1：12-5 -6-2-3
堆 2：15-13-4-1-0
我們將首先比較 15 和 12。寫 15
結果堆：15
現在比較 13 和 12
結果堆：15 - 13
比較 4 和 12
結果堆：15 - 13 - 12
比較 4 和 5
結果堆：15 - 13 - 12 - 4
如果我們繼續這樣下去，我們有
resultHeap : 15 - 13 - 12 - 5 - 6 - 4 - 2 - 3 - 1 - 0. 它也是一個堆
這個演算法正確嗎？或者有人可以給出反駁資料集嗎？
uj5u.com熱心網友回復：
這個演算法正確嗎？
不。
有人可以給出反駁資料集嗎？
接受這個輸入：
第一個堆：10、2、9
10 / \ 2 9第二堆：8、1、4
8 / \ 1 4
應用演算法——括號表示每個堆中的當前索引：
| 堆 1 | 堆 2 | 結果堆 |
|---|---|---|
| [10],2,9 | [8],1,4 | 10 |
| 10,[2],9 | [8],1,4 | 10,8 |
| 10,[2],9 | 8,[1],4 | 10,8,2 |
| 10,2,[9] | 8,[1],4 | 10,8,2,9（違規） |
| 10,2,9[] | 8,[1],4 | 10,8,2,9,1 |
| 10,2,9[] | 8,1,[4] | 10,8,2,9,1,4（違規） |
10
/ \
8 2
/ \ /
9 1 4
結果不是一個有效的堆，因為 9 不應該是 8 的孩子，因為 9 更大。并且 4 不應該是 2 的孩子，因為 4 更大。
uj5u.com熱心網友回復：
這可能是一種可能的解決方案。
- 假設 2 個最大（或最小）二進制堆（A 和 B）。
- 首先比較根，較小的一個（假設 A）可以安全地假設為另一個（B）的子樹的候選者，因此將其分配為 B 的任何一個子樹（假設左）
- 由于 B 的孩子現在被替換，你有 2 個新堆要考慮，即 B 的原始孩子
- 現在你有一個空白空間，即 B 的右孩子。遞回地按照這個程序合并 B 的孩子并將結果堆分配為 B 的右孩子。
這只是花哨的指標操作，實際上并沒有構建堆，而是利用了您已經擁有堆的事實。
抱歉不能更正式地表達它。如果您發現有問題，請糾正我。這只是總體思路，不考慮具體實作細節。
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/478621.html