堆排序 核心原理與 Java 手寫實現全解析

堆的定義與性質

• 完全二叉樹：除最後一層外每層滿，最後一層靠左排列；
• 數組存儲：索引 0 為根，左子節點 2i+1，右子節點 2i+2，父節點 (i-1)/2；
• 大頂堆：每個節點 ≥ 其子節點，根節點為最大值；
• 小頂堆：每個節點 ≤ 其子節點，根節點為最小值（常用於優先隊列）。

算法三大核心步驟

1. 建堆：從最後一個非葉子節點 (n/2-1) 向前依次 maxHeapify，自下而上構建大頂堆；
2. 排序：交換堆頂(最大)與末尾元素，堆尺寸 -1，對新堆頂 maxHeapify，重複至尺寸為 1；
3. 調整：maxHeapify(i) 保證以 i 為根的子樹滿足大頂堆性質，若子節點更大則交換並遞歸向下。

Java 完整實現

public class HeapSort {
    private int left(int i) { return 2 * i + 1; }
    private int right(int i) { return 2 * i + 2; }

    // 維護大頂堆性質
    public void maxHeapify(int[] heap, int i, int size) {
        int l = left(i), r = right(i), largest = i;
        if (l < size && heap[l] > heap[largest]) largest = l;
        if (r < size && heap[r] > heap[largest]) largest = r;
        if (largest != i) {
            swap(heap, i, largest);
            maxHeapify(heap, largest, size); // 遞歸向下
        }
    }

    // 建堆
    public void buildHeap(int[] heap) {
        for (int i = heap.length / 2 - 1; i >= 0; i--) {
            maxHeapify(heap, i, heap.length);
        }
    }

    // 堆排序入口
    public void sort(int[] heap) {
        buildHeap(heap);
        for (int i = heap.length - 1; i > 0; i--) {
            swap(heap, 0, i);           // 最大值換到末尾
            maxHeapify(heap, 0, i);     // 縮小堆範圍，調整新堆頂
        }
    }

    private void swap(int[] a, int i, int j) {
        int t = a[i]; a[i] = a[j]; a[j] = t;
    }

    public static void main(String[] args) {
        int[] arr = {4, 1, 5, 3, 7, 12, 65, 7};
        new HeapSort().sort(arr);
        System.out.println(Arrays.toString(arr)); // [1, 3, 4, 5, 7, 7, 12, 65]
    }
}

複雜度與特性

工程應用場景

• 海量數據 Top-K：建小頂堆維護 K 個最大值，單次 O(log K)；
• 外部排序：內存不足時，歸併階段利用堆選最小；
• 優先隊列底層：JDK PriorityQueue 即基於小頂堆。

手寫堆排序是理解「完全二叉樹隱式結構 + 自下而上構建 + 原地交換」三位一體設計的最佳練習。