使用Java實現堆排序算法

堆排序是一種基於堆數據結構的高效排序算法，它利用大頂堆（父節點值大於子節點值的完全二叉樹）每次取出最大值，逐步將數組排序。堆排序的時間複雜度爲O(n log n)，空間複雜度爲O(1)，是一種原地排序算法，適合處理大規模數據。

堆的概念¶

堆是一種特殊的完全二叉樹，分爲大頂堆和小頂堆：
- 大頂堆：每個父節點的值都大於或等於其子節點的值（如金字塔，頂部最大）。
- 小頂堆：每個父節點的值都小於或等於其子節點的值。

堆排序使用大頂堆，核心思想是：每次取出堆頂的最大值，放到數組末尾，再調整剩餘元素形成新的大頂堆，重複操作直到數組有序。

實現步驟¶

構建大頂堆：將無序數組調整爲大頂堆，使最大值位於堆頂（數組首元素）。
調整堆（heapify）：取出堆頂最大值後，調整剩餘元素的結構，保持大頂堆性質。
排序過程：交換堆頂與數組末尾元素，縮小堆的範圍，重複調整堆，直到排序完成。

核心函數實現¶

1. 調整堆（heapify）¶

功能：以指定節點爲根，調整子樹爲大頂堆。
參數：數組、堆大小、當前節點索引。
邏輯：比較當前節點與左右子節點，將最大子節點上移，遞歸調整子樹。

private static void heapify(int[] arr, int heapSize, int index) {
    int largest = index; // 假設當前節點是最大值
    int leftChild = 2 * index + 1; // 左子節點索引
    int rightChild = 2 * index + 2; // 右子節點索引

    // 找到左右子節點中的最大值
    if (leftChild < heapSize && arr[leftChild] > arr[largest]) {
        largest = leftChild;
    }
    if (rightChild < heapSize && arr[rightChild] > arr[largest]) {
        largest = rightChild;
    }

    // 若最大值不是當前節點，交換並遞歸調整子樹
    if (largest != index) {
        int temp = arr[index];
        arr[index] = arr[largest];
        arr[largest] = temp;
        heapify(arr, heapSize, largest);
    }
}

2. 構建大頂堆¶

功能：從最後一個非葉子節點開始，逐步向前調整每個節點，使整個數組成爲大頂堆。
邏輯：最後一個非葉子節點的索引爲 n/2 - 1（n爲數組長度），從該節點開始向前調用heapify。

private static void buildMaxHeap(int[] arr) {
    int n = arr.length;
    // 從最後一個非葉子節點開始調整
    for (int i = n / 2 - 1; i >= 0; i--) {
        heapify(arr, n, i);
    }
}

3. 堆排序主函數¶

功能：先構建大頂堆，再通過交換堆頂與末尾元素、調整堆，完成排序。
邏輯：
- 構建大頂堆後，最大值在堆頂（arr[0]）。
- 循環將堆頂元素與數組末尾元素交換，堆大小減1，調整剩餘元素爲大頂堆，重複直到排序完成。

public static void heapSort(int[] arr) {
    buildMaxHeap(arr); // 第一步：構建大頂堆

    // 第二步：排序過程
    for (int i = arr.length - 1; i > 0; i--) {
        // 交換堆頂（最大值）與當前末尾元素
        int temp = arr[0];
        arr[0] = arr[i];
        arr[i] = temp;

        // 調整剩餘元素爲大頂堆
        heapify(arr, i, 0);
    }
}

完整代碼與測試¶

import java.util.Arrays;

public class HeapSort {

    // 調整子樹爲大頂堆
    private static void heapify(int[] arr, int heapSize, int index) {
        int largest = index;
        int leftChild = 2 * index + 1;
        int rightChild = 2 * index + 2;

        if (leftChild < heapSize && arr[leftChild] > arr[largest]) {
            largest = leftChild;
        }
        if (rightChild < heapSize && arr[rightChild] > arr[largest]) {
            largest = rightChild;
        }

        if (largest != index) {
            int temp = arr[index];
            arr[index] = arr[largest];
            arr[largest] = temp;
            heapify(arr, heapSize, largest);
        }
    }

    // 構建大頂堆
    private static void buildMaxHeap(int[] arr) {
        int n = arr.length;
        for (int i = n / 2 - 1; i >= 0; i--) {
            heapify(arr, n, i);
        }
    }

    // 堆排序主函數
    public static void heapSort(int[] arr) {
        buildMaxHeap(arr);
        for (int i = arr.length - 1; i > 0; i--) {
            int temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;
            heapify(arr, i, 0);
        }
    }

    // 測試
    public static void main(String[] args) {
        int[] arr = {12, 11, 13, 5, 6, 7};
        System.out.println("排序前：" + Arrays.toString(arr));
        heapSort(arr);
        System.out.println("排序後：" + Arrays.toString(arr));
    }
}

輸出結果¶

排序前：[12, 11, 13, 5, 6, 7]
排序後：[5, 6, 7, 11, 12, 13]

總結¶

堆排序通過構建大頂堆和反覆調整堆，實現了高效排序。其核心在於heapify函數的遞歸調整，確保每次操作都能維護堆的性質。堆排序適用於大規模數據排序，尤其在空間受限的場景中表現優異。初學者可通過逐步理解構建堆、調整堆、排序三個步驟，掌握其實現邏輯。