在 C++ 中使用 STL 堆演算法
本文將演示如何在 C++ 中使用 STL 堆演算法。
使用 std::make_heap 函式將範圍轉換為堆
std::make_heap 函式是在 STL 演算法下提供的，它可以用來從給定的範圍構造一個二叉堆資料結構。通常，堆資料結構是基於樹的，兩種常見型別稱為最大堆和最小堆。
在最大堆中，對於任何子節點，其父節點的鍵大於或等於子節點的鍵。另一方面，父項的鍵小於等於子項的鍵。現在，用 make_heap 函式構造的堆結構是一個類似於二叉樹資料結構的二叉堆。請注意，堆對於元素插入和刪除操作是有效的，可以在對數時間內執行。
以下示例演示了將 std::vector 程序轉換為堆，然後使用通常的 printVector 函式列印內容。請注意，元素的順序有點神祕。實際上，你可以將它們讀作二叉樹結構，其中第一個元素是根鍵值。
由於二叉樹中的每個節點最多隻有兩個孩子，82 和 39 作為孩子跟隨根。接下來的兩個元素是 82 的子節點，另外兩個元素位於 39 下。此層次結構滿足最大堆屬性，即父元素的鍵大於或等於其子元素。
#include <iostream>
#include <algorithm>
#include <vector>
using std::cout; using std::endl;
using std::string; using std::vector;
template<typename T>
void printVector(const vector<T> &vec) {
for (auto &i : vec) {
cout << i << "; ";
}
cout << endl;
}
int main() {
vector<int> vec1 { 11, 82, 39, 72, 51, 32, 91 };
cout << "vec1 original: ";
printVector(vec1);
std::make_heap(vec1.begin(), vec1.end());
cout << "vec1 make_heap: ";
printVector(vec1);
return EXIT_SUCCESS;
}
輸出：
vec1 original: 11; 82; 39; 72; 51; 32; 91;
vec1 make_heap: 91; 82; 39; 72; 51; 32; 11;
使用 std::sort_heap 函式對堆範圍進行排序
你可以利用 std::sort_heap 函式使用 std::make_heap 函式對先前轉換的範圍進行排序。std::sort_heap 函式的簡單過載，只需要兩個迭代器引數，將範圍按升序排序。函式的另一個過載可以接受帶有以下簽名的比較函式的第三個引數：bool cmp(const Type1 &a, const Type2 &b);。範圍排序後，它不再具有堆屬性。
#include <iostream>
#include <algorithm>
#include <vector>
using std::cout; using std::endl;
using std::string; using std::vector;
template<typename T>
void printVector(const vector<T> &vec) {
for (auto &i : vec) {
cout << i << "; ";
}
cout << endl;
}
int main() {
vector<int> vec1 { 11, 82, 39, 72, 51, 32, 91 };
std::make_heap(vec1.begin(), vec1.end());
printVector(vec1);
std::sort_heap(vec1.begin(), vec1.end());
printVector(vec1);
return EXIT_SUCCESS;
}
輸出：
91; 82; 39; 72; 51; 32; 11;
11; 32; 39; 51; 72; 82; 91;
使用 std::pop_heap 函式刪除堆中的下一個元素
堆結構通常支援快速的元素插入和刪除操作。std::push_heap 和 std::pop_heap 函式相應地對堆範圍執行這些操作。當在堆範圍內呼叫 std::push_heap 命令時，它的第一個元素與最後一個位置交換，並用剩餘的元素構造一個新的堆。請注意，預設引數將堆構造為最大堆。可以傳遞一個可選的比較函式作為第三個引數來相應地修改堆層次結構。
#include <iostream>
#include <algorithm>
#include <vector>
using std::cout; using std::endl;
using std::string; using std::vector;
template<typename T>
void printVector(const vector<T> &vec) {
for (auto &i : vec) {
cout << i << "; ";
}
cout << endl;
}
int main() {
vector<int> vec1 { 11, 82, 39, 72, 51, 32, 91 };
std::make_heap(vec1.begin(), vec1.end());
printVector(vec1);
std::pop_heap(vec1.begin(), vec1.end());
printVector(vec1);
return EXIT_SUCCESS;
}
輸出：
91; 82; 39; 72; 51; 32; 11;
82; 72; 39; 11; 51; 32; 91;
Founder of DelftStack.com. Jinku has worked in the robotics and automotive industries for over 8 years. He sharpened his coding skills when he needed to do the automatic testing, data collection from remote servers and report creation from the endurance test. He is from an electrical/electronics engineering background but has expanded his interest to embedded electronics, embedded programming and front-/back-end programming.
LinkedIn