您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> C++ >> 關於C++

C++ 最大堆實現詳解：從數組建堆到動態操作

編輯：關於C++

最大堆數據結構核心概念

最大堆是一種特殊的完全二叉樹，其中每個父節點的值都大於或等於其子節點的值。這種結構使得根節點始終存儲著整個堆中的最大值，因此最大堆常被用於實現優先隊列、堆排序以及尋找第 K 大元素等場景。在 C++ 中，我們可以通過模板類來實現一個通用的最大堆，支持任意可比較的數據類型。

核心代碼實現

以下是一個完整的最大堆模板類實現，包含了構造函數（數組建堆）、插入、刪除堆頂、獲取堆頂元素等核心操作：

#include <iostream>
#include <vector>
#include <algorithm> // for std::swap
using namespace std;

template <class T>
class Heap {
public:
    // 使用數組初始化堆（O(n) 建堆）
    Heap(T* arr, size_t size) {
        _arr.reserve(size);
        for (size_t i = 0; i < size; ++i) {
            _arr.push_back(arr[i]);
        }
        // 從最後一個非葉節點開始向下調整
        for (int i = (static_cast<int>(_arr.size()) - 2) / 2; i >= 0; --i) {
            AdjustDown(i);
        }
    }

    // 插入新元素
    void Push(const T& data) {
        _arr.push_back(data);
        AdjustUp(_arr.size() - 1);
    }

    // 刪除堆頂元素
    void Pop() {
        if (_arr.empty()) return;
        swap(_arr[0], _arr[_arr.size() - 1]);
        _arr.pop_back();
        if (!_arr.empty()) {
            AdjustDown(0);
        }
    }

    // 獲取堆頂元素
    const T& Top() const {
        return _arr[0];
    }

    // 獲取堆大小
    size_t Size() const {
        return _arr.size();
    }

    // 判斷堆是否為空
    bool Empty() const {
        return _arr.empty();
    }

    // 顯示堆中所有元素
    void Display() const {
        for (size_t i = 0; i < _arr.size(); ++i) {
            cout << _arr[i] << " ";
        }
        cout << endl;
    }

private:
    vector<T> _arr;

    // 向下調整：維持以 root 為根的子樹滿足大堆性質
    void AdjustDown(size_t root) {
        size_t parent = root;
        size_t child = 2 * parent + 1; // 左孩子

        while (child < _arr.size()) {
            // 找出左右孩子中較大的那個
            if (child + 1 < _arr.size() && _arr[child + 1] > _arr[child]) {
                ++child;
            }
            // 如果孩子大於父親，則交換並繼續向下
            if (_arr[child] > _arr[parent]) {
                swap(_arr[child], _arr[parent]);
                parent = child;
                child = 2 * parent + 1;
            } else {
                break; // 已滿足堆性質
            }
        }
    }

    // 向上調整：新插入的節點向上浮動
    void AdjustUp(size_t child) {
        size_t parent = (child - 1) / 2;
        while (child > 0) { // child > 0 確保 parent 有效
            if (_arr[child] > _arr[parent]) {
                swap(_arr[child], _arr[parent]);
                child = parent;
                parent = (child - 1) / 2;
            } else {
                break;
            }
        }
    }
};

// 測試用例
void test() {
    int arr[] = {10, 11, 13, 12, 16, 18, 15, 17, 14, 19};
    int size = sizeof(arr) / sizeof(arr[0]);
    Heap<int> hp(arr, size);
    
    cout << "初始堆: ";
    hp.Display(); // 預期: 19 17 18 12 16 13 15 10 14 11

    hp.Push(20);
    cout << "插入 20 後: ";
    hp.Display(); // 堆頂變為 20

    hp.Pop();
    cout << "刪除堆頂後: ";
    hp.Display(); // 堆頂恢復為次大值

    cout << "size = " << hp.Size() << endl;
}

int main() {
    test();
    return 0;
}

關鍵算法解析

1. 數組建堆 - O(n) 時間複雜度

構造函數中採用了經典的「自底向上」建堆策略。從最後一個非葉節點 (size-2)/2 開始，依次對每個節點調用 AdjustDown。雖然單次向下調整最壞情況為 O(log n)，但數學證明表明，對所有非葉節點執行此操作的總時間複雜度為 O(n)，遠優於依次插入的 O(n log n)。

2. 向下調整

AdjustDown 是維持堆性質的核心。它比較父節點與其左右孩子，若孩子較大則交換，並繼續向下遞歸/迭代。注意邊界條件：child + 1 < _arr.size() 確保右孩子存在才進行比較。

3. 向上調整

AdjustUp 用於插入新元素後恢復堆性質。新元素置於數組末尾，不斷與父節點比較，若較大則交換，直到到達根節點或滿足堆性質。

4. 刪除堆頂

Pop 操作將堆頂與末尾元素交換，移除末尾（原堆頂），然後對新根節點執行 AdjustDown。這保證了刪除後堆仍保持完全二叉樹結構和大堆性質。

應用場景與擴展

優先隊列：C++ STL priority_queue 底層即為最大堆。
堆排序：反覆彈出堆頂即可得到降序序列。
Top-K 問題：維持大小為 K 的最小堆（或用最大堆配合邏輯）高效求解。
中位數維護：雙堆（大頂堆+小頂堆）動態維護數據流中位數。

常見錯誤與優化提示

邊界檢查：AdjustDown 中 child 計算需防止溢出，使用 size_t 需注意 child < _arr.size() 條件。
空堆保護：Pop 和 Top 應檢查 Empty()，避免未定義行為。
泛型支持：模板參數 T 需支持 > 比較運算符，或通過仿函數自定義比較邏輯。
引用返回：Top() 返回 const T& 避免拷貝，但需注意生命週期。