使用C++實現堆排序算法

堆排序算法的C++實現¶

堆排序是一種基於堆數據結構的高效排序算法，它利用堆的特性（完全二叉樹的結構），通過反覆調整堆來實現排序。堆排序的時間複雜度爲O(n log n)，空間複雜度爲O(1)，適合處理大規模數據。

一、堆的基本概念¶

堆是一種特殊的完全二叉樹，分爲大頂堆和小頂堆：
- 大頂堆：每個父節點的值大於或等於其子節點的值（父 >= 子）。
- 小頂堆：每個父節點的值小於或等於其子節點的值（父 <= 子）。

堆排序通常使用大頂堆，因爲每次可以取出堆頂的最大值。

二、堆的存儲結構¶

堆可以用數組表示，數組的索引與節點位置的關係如下：
- 對於數組中索引爲 i 的節點：
- 父節點索引：(i - 1) / 2（向下取整）
- 左子節點索引：2 * i + 1
- 右子節點索引：2 * i + 2

例如，數組 [12, 11, 13, 5, 6, 7] 對應的堆結構爲：

三、堆排序的核心步驟¶

堆排序分爲兩步：構建初始大頂堆和排序過程。

構建初始大頂堆：將無序數組調整爲大頂堆。從最後一個非葉子節點開始，逐個向上調整，確保每個子樹滿足大頂堆性質。
排序過程：
- 交換堆頂（最大值）與未排序部分的最後一個元素。
- 縮短未排序部分的長度，調整堆（向下調整）。
- 重複上述步驟，直到所有元素排序完成。

四、C++代碼實現¶

#include <iostream>
#include <vector>
using namespace std;

// 交換兩個元素的值
void swap(int& a, int& b) {
    int temp = a;
    a = b;
    b = temp;
}

// 調整以i爲根的子樹爲大頂堆（迭代實現）
void max_heapify(vector<int>& arr, int n, int i) {
    while (true) {
        int largest = i; // 當前節點爲最大值
        int left = 2 * i + 1; // 左子節點索引
        int right = 2 * i + 2; // 右子節點索引

        // 比較左子節點是否更大
        if (left < n && arr[left] > arr[largest]) {
            largest = left;
        }
        // 比較右子節點是否更大
        if (right < n && arr[right] > arr[largest]) {
            largest = right;
        }
        // 如果最大值不是當前節點，交換並繼續調整
        if (largest != i) {
            swap(arr[i], arr[largest]);
            i = largest; // 調整被交換的子節點
        } else {
            break; // 已滿足大頂堆性質，停止調整
        }
    }
}

// 堆排序主函數
void heap_sort(vector<int>& arr) {
    int n = arr.size();

    // 步驟1：構建初始大頂堆
    // 從最後一個非葉子節點開始向上調整
    for (int i = n / 2 - 1; i >= 0; --i) {
        max_heapify(arr, n, i);
    }

    // 步驟2：排序過程
    for (int i = n - 1; i > 0; --i) {
        // 交換堆頂（最大值）與未排序部分的末尾元素
        swap(arr[0], arr[i]);
        // 調整剩餘部分的堆（長度爲i）
        max_heapify(arr, i, 0);
    }
}

int main() {
    // 測試用例
    vector<int> arr = {12, 11, 13, 5, 6, 7};
    cout << "排序前的數組：";
    for (int num : arr) {
        cout << num << " ";
    }
    cout << endl;

    // 調用堆排序
    heap_sort(arr);

    // 輸出排序結果
    cout << "排序後的數組：";
    for (int num : arr) {
        cout << num << " ";
    }
    cout << endl;

    return 0;
}

五、代碼解析¶

swap函數：簡單交換兩個整數的值。
max_heapify函數：確保以 i 爲根的子樹滿足大頂堆性質。通過迭代比較當前節點與子節點，若子節點更大則交換，直到子樹滿足大頂堆條件。
heap_sort函數：
- 構建堆：從最後一個非葉子節點（n/2 - 1）開始，逐個向上調用 max_heapify，形成初始大頂堆。
- 排序：將堆頂（最大值）與未排序部分的末尾元素交換，縮短未排序部分長度，再次調用 max_heapify 調整堆，重複直到所有元素排序完成。

六、運行結果¶

排序前的數組：12 11 13 5 6 7 
排序後的數組：5 6 7 11 12 13

堆排序通過高效利用堆的特性，實現了穩定的O(n log n)時間複雜度，是一種經典的排序算法。初學者可通過逐步理解堆的構建和調整過程，掌握其核心思想。