什麼是最小堆的平均時間成本

Question

查看我的測試數據結構我注意到某些東西時，它可以請求幫助和答案，什麼是平均時間成本（大O）搜索最大鍵入最小堆（優先級隊列），是O（log N）還是O（N）？

Answer 1

在最小堆中搜索最大元素是O(N)。

你必須去樹的最低層（這是最多一半的孩子），並檢查它們中的每一個，因爲它們沒有特定的順序相互關聯。

這將需要檢查約N/2節點（假設您使用標準算法來查找最大值）是O(N)。

如果您有興趣在堆中查找最大元素，則可以使用最大堆代替。如果內存不是一個大問題，你可以使用最大堆和最小堆，這將允許你獲得最大和最小元素。