申論題 - 阿摩線上測驗

申論題資訊

試卷：111年 - 111 地方政府特種考試_三等_資訊處理：資料結構#112604
科目：公職◆資料結構
年份：111年
排序：0

四、二元堆積（BinaryHeap）是一種優先佇列（PriorityQueue），主要用來管理具有優先權順序的資料物件，每個資料物件具有一個可以界定大小或前後順序的鍵值（Key），我們在此假設鍵值越低的資料物件有越高的優先權。

(三)若有兩個二元樹T₁及T₂，其節點具有堆積特性且高度分別是O(logn) 與O(logm)，請提供一個方法將此兩個二元樹結合成為一個節點具有堆積特性的二元樹T，此方法的時間須為O(logn+logm)。（10分）

詳解提供者：WJ

可以參考左撇子樹的合併方式

1. 將兩棵樹的root值比較，假設root值比較小的為T1，另一棵為T2
2. T1的root與左子樹保留成新樹T的root與左子樹，而右子樹目前為空
3. 將原本T1的右子樹與T2做合併，合併結果放在T的右子樹