第 二 題

作答時應先思考『未排序陣列』的資料結構特性：插入時因無需維持順序，可直接附加於陣列末端；但取最大值時，因資料缺乏順序性，必須循序搜尋整個陣列才能找到目標。依據此結構操作特性推導時間複雜度即可精準拿分。

看到「排序好的陣列」，首先思考其物理結構特性：極值必定在陣列兩端，因此讀取極快；但陣列在記憶體中是連續儲存的，插入新元素為維持排序狀態，必須挪動後續元素，產生較高的時間開銷。

看到此題應先聯想最大堆積（Max-Heap）本質上是一棵完全二元樹（Complete Binary Tree），其樹高為 O(log n)。接著思考插入（Insert）與取出最大值（Extract-Max）時的資料重整過程（Heapify-up 與 Heapify-down），即可推導出兩者的時間複雜度皆與樹高成正比。

看到最大堆積（Max Heap），應立即聯想其兩大特性：(1) 形狀為完全二元樹 (Complete Binary Tree)；(2) 任何父節點的值必大於或等於其子節點。實作時，新增元素放在樹的最底層最後方，並執行『向上調整 (Up-Heap)』；取出最大值時，移除根節點，將最後一個節點移至根部，並執行『向下調整 (Down-Heap)』。