C++ STL 堆算法完全指南：make_heap、push_heap、pop_heap、sort_heap 實戰詳解

前言

<algorithm> 提供四大堆算法，基於**隨機訪問迭代器**的容器（vector、deque、數組）即可構建堆結構，無需手動實現複雜的上浮/下沉邏輯。本文詳細講解 make_heap、push_heap、pop_heap、sort_heap、is_heap 的用法、參數、時間複雜度、實戰代碼與常見誤區。

一、核心算法速查表

二、比較器與堆類型

• 默認 less：構建**最大堆**，堆頂為**最大值**（*begin() 最大）。
• greater：構建**最小堆**，堆頂為**最小值**。
• 自定義比較器：make_heap(v.begin(), v.end(), [](int a, int b){ return a > b; }) 同 greater。

三、完整實戰代碼演示

#include 
#include 
#include 
#include  // less, greater
using namespace std;

void print(const vector& v, const string& label) {
    cout << label << ": ";
    for (int x : v) cout << x << ' ';
    cout << " | is_heap: " << is_heap(v.begin(), v.end()) << endl;
}

int main() {
    // 1. 初始數據
    int arr[] = {4, 5, 6, 7, 8, 1};
    vector v(arr, arr + 6);
    print(v, "Original");

    // 2. 構建最大堆
    make_heap(v.begin(), v.end(), less());
    print(v, "After make_heap (max-heap)");

    // 3. 插入元素 100
    v.push_back(100);        // 先放到容器末尾
    push_heap(v.begin(), v.end(), less()); // 再上浮調整
    print(v, "After push 100");

    // 4. 彈出堆頂 (最大值)
    pop_heap(v.begin(), v.end(), less()); // 將堆頂移到末尾，剩餘調整為堆
    cout << "Popped max: " << v.back() << endl; // 訪問末尾元素
    v.pop_back();             // 真正刪除
    print(v, "After pop_heap");

    // 5. 堆排序 (得到升序序列)
    sort_heap(v.begin(), v.end(), less());
    print(v, "After sort_heap (ascending)");
    // 注意：sort_heap 後不再是堆，is_heap 為 false

    // 6. 最小堆示例
    vector minHeap = {5, 2, 8, 1, 9};
    make_heap(minHeap.begin(), minHeap.end(), greater());
    print(minHeap, "Min-heap");
    minHeap.push_back(0);
    push_heap(minHeap.begin(), minHeap.end(), greater());
    print(minHeap, "Min-heap after push 0");
    pop_heap(minHeap.begin(), minHeap.end(), greater());
    cout << "Popped min: " << minHeap.back() << endl;
    minHeap.pop_back();
    print(minHeap, "Min-heap after pop");

    return 0;
}

四、關鍵操作流程圖解

1. push_heap 插入流程

容器: [heap elements...] new_elem
        ↑
push_back(new_elem)  // 1. 放到末尾
push_heap(begin, end) // 2. 從末尾向上比較交換，直到滿足堆性質

2. pop_heap 刪除流程

容器: [heap_top, ... , last]
        ↑
pop_heap(begin, end) // 1. swap(heap_top, last) → 堆頂移到末尾
                     // 2. 對 [begin, end-1) 下沉調整，恢復堆性質
                     // 3. 返回，原堆頂現位於 end-1
容器: [new_heap..., old_top]
                     ↑
v.pop_back()         // 3. 真正刪除原堆頂

3. sort_heap 排序原理

重複執行 pop_heap 直到堆大小為 1：
pop_heap → 最大值移到末尾 → 縮小範圍
最終容器變為升序序列 (若用 less 即最大堆)

五、優先隊列 priority_queue vs 手動堆算法

六、常見錯誤與避雷指南

1. 忘記 push_back 再 push_heap：push_heap 假設新元素已在末尾，直接操作現有範圍。
2. pop_heap 後未 pop_back：pop_heap 僅將堆頂移到末尾並調整剩餘，**不改變容器大小**。
3. sort_heap 後繼續用作堆：sort_heap 破壞堆結構，轉為有序序列，不可再調用 push_heap/pop_heap。
4. 比較器不一致：構建、插入、刪除、排序**必須使用相同比較器**，否則行為未定義。
5. 非隨機訪問迭代器容器：list/forward_list **不能**直接用堆算法，需先拷貝到 vector。
6. 空範圍調用：pop_heap/sort_heap 要求範圍非空，否則未定義行為。

七、實戰場景：Top K 問題

// 求數組中前 K 大元素 (K << N)
vector topK(const vector& nums, int k) {
    vector heap(nums.begin(), nums.begin() + k);
    make_heap(heap.begin(), heap.end(), greater()); // 最小堆，堆頂最小
    
    for (size_t i = k; i < nums.size(); ++i) {
        if (nums[i] > heap[0]) { // 比堆頂大，替換
            heap[0] = nums[i];
            push_heap(heap.begin(), heap.end(), greater());
        }
    }
    sort_heap(heap.begin(), heap.end(), greater()); // 降序輸出
    return heap;
}

時間複雜度 O(N log K)，空間 O(K)，適合海量數據流式處理。