最小堆時間復雜度

最小堆（Min Heap）是一種特殊的二叉樹，滿足下列條件：

1. 堆中任一非葉節點的值均不超過（或等於）其任何孩子節點的值。
2. 堆的結構滿足完全二叉樹的特性，即除最底層外，每一層的節點都是滿的，且最底層的節點盡可能填滿左側。

最小堆可以用來實作優先佇列（Priority Queue），具有以下操作：

• 插入（Insert）：將一個新元素插入到堆中。
• 刪除最小（Extract Min）：刪除堆中值最小的元素。
• 檢索最小（Find Min）：找到堆中值最小的元素，但不刪除它。
• 更新（Update）：更新堆中的一個元素的值。

這些操作的時間複雜度都是 O(log n)，其中 n 是堆中元素的數量。這個時間複雜度是由於最小堆的結構特性和操作的對數性質決定的。例如，在最小堆中刪除最小元素涉及將最後一個元素替換為刪除的元素，然後對樹進行修復，使其重新成為最小堆，這可以在 O(log n) 時間內完成。

需要注意的是，這個時間複雜度是在最壞情況下的，即堆的結構保持平衡。如果堆結構嚴重偏斜，某些操作可能需要更長的時間，但在實際應用中，堆通常會保持平衡，因此 O(log n) 的時間複雜度是一個穩定的估計。