地特三等申論題
114年
[資訊處理] 資料結構
第 題
📖 題組：
二、Priority Queue（優先佇列）是一種「每次取出的元素都是優先權最高的」資料結構。
二、Priority Queue（優先佇列）是一種「每次取出的元素都是優先權最高的」資料結構。
如果用「排序好的陣列」來實作優先佇列，插入與取最大值的時間複雜度為何？（5 分）
📝 此題為申論題
思路引導 VIP
思考「排序好的陣列」的物理結構。如果我們要把新元素插入到一個已經排好序的陣列中，為了維持排序狀態，我們必須透過線性搜尋找到合適位置，並將其後的元素向後平移，這需要 O(n) 的時間。但因為陣列已經排好序，最大值一定在陣列的兩端（依遞增或遞減排序而定），取出的時間只需要 O(1)。