在 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