地特三等申論題
114年
[資訊處理] 資料結構
第 題
📖 題組：
二、Priority Queue（優先佇列）是一種「每次取出的元素都是優先權最高的」資料結構。
二、Priority Queue（優先佇列）是一種「每次取出的元素都是優先權最高的」資料結構。
如果用「未排序陣列」，來實作優先佇列，插入與取最大值的時間複雜度為何？（5 分）
📝 此題為申論題
思路引導 VIP
思考「未排序陣列」的物理結構。因為不需維持順序，所以插入新元素可以直接放在陣列的最末端，動作極為快速。然而，當需要取出最大值時，因為資料雜亂無章，我們必須遍歷整個陣列來尋找最大值，這需要線性的時間。