c++ - 在 C++ 中实现最大和最小堆

Question

因此，为了制作最大堆，我可以执行以下操作:

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 ？

其次，这是为了制作最大堆。最小堆有类似的东西吗？谢谢!

Answer 1

将一个元素插入堆是一个两步过程。首先，您需要在代表堆的容器后面插入一个元素。标准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;
}