地特三等申論題
111年
[資訊處理] 資料結構
第 一 題
📖 題組：
二元堆積（Binary Heap）是一種優先佇列（Priority Queue），主要用來管理具有優先權順序的資料物件，每個資料物件具有一個可以界定大小或前後順序的鍵值（Key），我們在此假設鍵值越低的資料物件有越高的優先權。
二元堆積（Binary Heap）是一種優先佇列（Priority Queue），主要用來管理具有優先權順序的資料物件，每個資料物件具有一個可以界定大小或前後順序的鍵值（Key），我們在此假設鍵值越低的資料物件有越高的優先權。
📝 此題為申論題，共 3 小題
小題 (一)
請完整描述最小堆積（Min_Heap）的定義與相關的操作功能。（5 分）
思路引導 VIP
看到「Min_Heap」應立即拆解為兩部分作答：先點出其兩大核心定義（結構性質為完全二元樹、順序性質為父節點小於等於子節點）；接著列出優先佇列必備的核心操作（Insert、Extract-Min、Get-Min），並附上對應的時間複雜度，即可穩拿基本分。
小題 (二)
請說明堆積排序（Heap Sort）的方法並分析其時間複雜度。（5 分）
思路引導 VIP
看到堆積排序（Heap Sort），應直覺聯想其兩大核心階段：「建立堆積（Build Heap）」與「逐步取出並調整（Extract & Heapify）」。作答時需條列式寫出排序步驟，並將時間複雜度拆分為建表與調整兩個部分進行精確分析，以展現嚴謹度。
小題 (三)
若有兩個二元樹 T1 及 T2，其節點具有堆積特性且高度分別是 O(log n) 與 O(log m)，請提供一個方法將此兩個二元樹結合成為一個節點具有堆積特性的二元樹 T，此方法的時間須為 O(log n+ log m)。（10 分）
思路引導 VIP
看到「將兩個具堆積特性的二元樹在 O(log n + log m) 時間內合併」，應立刻聯想到「左傾堆積 (Leftist Heap)」或「歪斜堆積 (Skew Heap)」的合併演算法 (Meld/Merge)。因為陣列實作的完全二元樹無法在對數時間內合併，本題放寬為「具堆積特性的二元樹」，故使用指標實作的遞迴合併法（比較根節點並往右子樹遞迴合併）即可達成時間複雜度的要求。