最小堆算法

最小堆（Min Heap）是一種特殊的完全二叉樹，其中每個節點的值都不大於其父節點的值。最小堆可以分為最大堆（Max Heap）和最小堆兩種，最大堆中每個節點的值都不小於其父節點的值。

最小堆算法用於實現一種優先佇列，其中插入操作的時間複雜度為O(log n)，刪除最小元素（即堆頂元素）的時間複雜度也為O(log n)。最小堆算法的基本操作包括插入新元素、刪除最小元素和調整堆。

最小堆的調整過程是通過交換子節點和父節點實現的，直到子節點不違反堆的性質為止。下面是一個簡單的最小堆調整過程的偽代碼示例：

function AdjustMinHeap(heap, i):
    n = size of heap
    while i < n and heap[i] < heap[(i + 1) / 2]:
        swap heap[i] and heap[(i + 1) / 2]
        i = (i + 1) / 2

這個函式的作用是將最小堆中第i個節點的子樹調整為最小堆。

最小堆的構建過程是將一組無序的元素構建成一個最小堆的過程。這個過程可以通過遞歸地調整每個新添加的元素來實現。下面是一個簡單的最小堆構建過程的偽代碼示例：

function BuildMinHeap(array):
    n = size of array
    for i in [n/2, 1, ..., 1]:
        AdjustMinHeap(array, i)

這個函式的作用是將數組array中的元素構建成一個最小堆。

最小堆算法在許多實際套用中都有廣泛的使用，例如：

1. 優先佇列：最小堆可以用來實現一個支持高效插入和刪除最小元素的優先佇列。
2. 排序：通過多次刪除最小元素，可以將最小堆轉換為一種排序算法。
3. 最短路徑：在圖論中，最小堆可以用來求解最短路徑問題，如Dijkstra算法。
4. 實時調度：在作業系統中，最小堆可以用來管理進程或執行緒的優先權調度。

最小堆算法的實現通常使用數組來存儲，因為這樣可以保證快速訪問任一節點，並且可以高效地支持插入和刪除操作。