堆積排序：生存競賽

演算法背後的故事：王權的邏輯

想像一個王國，國王必須是全國最強壯的人。當現任國王去世時，全國會舉行一場比武大賽。所有的公爵、騎士和士兵都在一個層級森嚴的對陣表中競爭。勝者成為新任國王。

但這裡有一個規則：一旦勝者加冕並被載入史冊，他就必須離開王國。現在，剩下的競爭者必須重新組織層級，尋找下一位最強領袖。

這就是 堆積排序 (HeapSort) 的精髓，由 J. W. J. Williams 在 1964 年發明。它不依賴於像快速排序那樣的「劃分世界」，也不依賴於像歸併排序那樣的「合併世界」。它依賴的是一套競爭性的層級制度（即「堆積」）。

為什麼需要它？

堆積排序是高效排序演算法中的「極簡主義者」。

• 原地排序： 與歸併排序不同，它不需要任何額外記憶體 ($O(1)$ 空間)。
• 穩定性： 這裡的穩定性指性能。和歸併排序一樣，它的速度始終是 $O(N \log N)$，永遠不會像快速排序那樣遇到「倒楣的一天」。
• 提取 TopK： 如果妳只需要 100 萬件商品中價格最高的 100 件，妳不需要排序全部。妳只需要執行 100 次「比武大賽」即可。

演算法是如何「思考」的

這個演算法像是一個嚴格的比賽組織者，負責維護一套嚴格的層級。

1. 海選 (建堆)： 它拿出一份隨機列表，強行將其塞入一個「大頂堆」結構中。在這個樹形結構裡，每個父親都必須比他的孩子更強大（數值更大）。此時，最強的元素就在最頂端。

2. 勝出 (提取)： 頂端的元素是獲勝者。它被移到列表的末尾（它的終身歸宿）。

3. 重組 (堆化)： 現在頂端空了。組織者從樹的最底層隨手抓起一個卑微的「平民」放在頂端。 可以預見，這個平民很弱。因此，他必須在層級中「下沉」，不斷與比他更強壯的孩子交換位置，直到層級秩序重新恢復。

4. 迴圈： 比賽繼續進行，直到只剩下最後一個人。

工程決策：優先佇列

在生產環境中，堆積的排序版本其實不如她的孿生兄弟——優先佇列 (Priority Queue) 常用。

• 作業系統： CPU 下一步該處理哪個任務？當然是優先級最高的那個。
• 串流數據： 即時尋找「前 10 名熱門話題」。堆積能保持前 10 名在頂端，讓妳高效地無視剩下的數百萬個「落選者」。

實作參考 (Python)

import heapq

def heapsort(arr):
    # Python 的 heapq 實作的是小頂堆 (Min-Heap)。
    # 如果我們要升序排列，可以直接利用她。
    h = []
    for value in arr:
        heapq.heappush(h, value)
    
    # 依次彈出最小值，即可得到有序列表
    return [heapq.heappop(h) for _ in range(len(h))]

# 原地邏輯範例 (手動堆化)
def heapify(arr, n, i):
    largest = i
    left = 2 * i + 1
    right = 2 * i + 2

    # 如果左孩子比父親大
    if left < n and arr[i] < arr[left]:
        largest = left
    # 如果右孩子比目前最大的還大
    if right < n and arr[largest] < arr[right]:
        largest = right

    # 如果最大的不是父親，交換並繼續向下調整
    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        heapify(arr, n, largest)

小結

堆積排序教會我們：秩序源於競爭。透過建立層級並系統性地選拔最優者，我們可以在不佔用額外空間的情況下達成完美的秩序。它提醒我們，即使面對數十億數據，有時我們也只需要知道「此刻誰是最好的」。