因此,为了制作最大堆,我可以执行以下操作:
int main () {
int myints[] = {10,20,30,5,15};
std::vector<int> v(myints,myints+5);
std::make_heap (v.begin(),v.end());
std::cout << "initial max heap : " << v.front() << '\n';
我有疑问。就像我使用 push_back 操作插入 vector 一样,有什么方法可以像那样插入最大堆吗?还是总是通过 vector ?
其次,这是为了制作最大堆。最小堆有类似的东西吗?谢谢!
最佳答案
将一个元素插入堆是一个两步过程。首先,您需要在代表堆的容器后面插入一个元素。标准push_back
会做。然后你需要使用 push_heap
,这基本上会在范围的最后一个元素上调用 upheap。
对于不同的顺序,您需要使用自定义版本的比较器。当第一个元素小于第二个时,默认值期望它返回 true。所以你需要颠倒逻辑。有几种方法可以做到这一点。我将 lambda 与显式 operator>
一起使用而不是 operator<
.可以使用一些更花哨的模板,或者使用 functional .
完整代码示例:
#include <iostream>
#include <algorithm>
int main() {
std::vector<int> v {10,20,30,5,15};
std::make_heap(v.begin(), v.end());
v.push_back(40);
std::push_heap(v.begin(), v.end()); // notice that now the v.end() points
// to different location than before
for (auto i : v) std::cout << i << ' ';
std::cout << '\n';
auto cmp = [](int a, int b) { return a>b; }; // custom comparator via lambda
std::make_heap(v.begin(), v.end(), cmp); // make a new heap using `cmp`
v.push_back(3); // add another element
std::push_heap(v.begin(), v.end(), cmp); // restore heap structure using `cmp`
for (auto i : v) std::cout << i << ' ';
return 0;
}
以 functional
为例的更大:
#include <iostream>
#include <algorithm>
#include <functional>
int main() {
std::vector<int> v {10,20,30,5,15};
auto cmp = std::greater<int>(); // make an instance of standard `greater` comparator
std::make_heap(v.begin(), v.end(), cmp); // make a new heap using `cmp`
v.push_back(3); // add another element
std::push_heap(v.begin(), v.end(), cmp); // restore heap structure using `cmp`
for (auto i : v) std::cout << i << ' ';
return 0;
}
关于c++ - 在 C++ 中实现最大和最小堆,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/26342914/