在 C++ 中使用 STL 堆演算法

使用 C++ STL 堆積演算法，可將 std::vector 範圍轉換為最大堆積、排序該範圍，或將其中最大值移至末尾。std::pop_heap 只會移動該值；若要從向量中移除它，還需另外刪除。

使用 std::make_heap 函式將範圍轉換為堆積

堆積是一種符合父子關係規則的範圍。使用預設比較方式時，std::make_heap 會建立最大堆積：每個父節點都大於或等於其子節點，因此最大值位於範圍開頭。對以向量表示的二元堆積而言，索引為 i 的元素，其子節點索引為 2 * i + 1 和 2 * i + 2，前提是這些位置仍在範圍內。最小堆積則使用不同的比較方式，例如 std::greater<int>。

std::make_heap 會重新排列元素以符合堆積性質，但不會將整個範圍排序。許多不同排列都可能符合相同的性質，因此程式應依賴開頭元素及父子節點間的比較，而不要假設呼叫後會得到某個特定的元素順序。

以下獨立範例會建立堆積並檢查父子節點規則。範例已成功執行，觀察到的輸出如下。

#include <algorithm>
#include <cstddef>
#include <iostream>
#include <vector>

int main() {
    std::vector<int> values{11, 82, 39, 72, 51, 32, 91};
    std::make_heap(values.begin(), values.end());

    bool is_max_heap = true;
    for (std::size_t child = 1; child < values.size(); ++child) {
        const std::size_t parent = (child - 1) / 2;
        if (values[parent] < values[child]) {
            is_max_heap = false;
            break;
        }
    }

    std::cout << "max-heap: " << std::boolalpha << is_max_heap << '\n';
    std::cout << "top: " << values.front() << '\n';
}

max-heap: true
top: 91

第一個元素是堆積的頂端值。向量中其餘元素的順序只受堆積性質限制，因此不能把它當成遞增或遞減的清單。

使用 std::sort_heap 函式排序堆積範圍

對已符合堆積性質的範圍呼叫 std::sort_heap。使用預設比較方式時，它會將範圍重新排列為遞增順序。排序後，該範圍便不再符合堆積性質；若要對整個範圍再次執行堆積操作，請先重新呼叫 std::make_heap。

例如，在呼叫 std::make_heap(values.begin(), values.end()) 之後，再呼叫 std::sort_heap(values.begin(), values.end()) 即可排序同一範圍。預設比較方式會產生遞增順序。

含比較器的多載版本可接受定義排序方式的函式或函式物件。建立及排序堆積時，請使用相同的比較方式；例如，以 std::greater<int> 建立的堆積，也必須使用該比較器排序。若目標是取得遞增結果，使用預設多載即可。

使用 std::pop_heap 函式移除堆積中的下一個元素

std::pop_heap 會將頂端值移至範圍的最後一個位置，並恢復前段範圍的堆積性質。它不會改變向量的大小。若要從容器中移除該值，請在呼叫 std::pop_heap 後再呼叫 pop_back()。

若要加入元素，請先將它附加至向量，再呼叫 std::push_heap。除了新附加元素以外的範圍必須已是堆積；接著 std::push_heap 會在擴大的範圍中恢復堆積性質。這兩個演算法都應使用定義該堆積的相同比較器。

以下獨立範例會檢查移至末尾的頂端值、另行刪除該值，然後在維持堆積性質的情況下加入新值。範例已成功執行，觀察到的輸出如下。

#include <algorithm>
#include <iostream>
#include <vector>

int main() {
    std::vector<int> values{11, 82, 39, 72, 51, 32, 91};
    std::make_heap(values.begin(), values.end());

    std::pop_heap(values.begin(), values.end());
    std::cout << "moved top: " << values.back() << '\n';
    values.pop_back();

    values.push_back(95);
    std::push_heap(values.begin(), values.end());
    std::cout << "new top: " << values.front() << '\n';
}

moved top: 91
new top: 95

呼叫 std::pop_heap 後，最後一個元素之前的前段範圍就是可繼續使用的堆積。pop_back() 移除末尾值後，向量本身便再次恰好包含該堆積範圍。若附加元素前沒有先維持這項性質，就不符合 std::push_heap 的前置條件。