我应该何时使用make_heap与Priority Queue？

Question

我有一个我想用来创建堆的向量.我不确定是否应该使用C++ make_heap函数或将我的向量放在优先级队列中？在性能方面哪个更好？我何时应该使用一个与另一个？

Answer 1

性能方面没有区别.std::priority_queue只是一个适配器类,它将容器和与堆相关的函数调用包装在一个类中.std::priority_queue公开说明的规范.

通过从公开的std::vector(通过直接调用与堆相关的函数)构建基于堆的优先级队列,可以保持对外部访问的可能性,从而可能破坏堆/队列的完整性.std::priority_queue作为屏障限制访问来"规范"最低:push(),pop(),top()等你可以把它看作自律执行措施.

此外,通过使您的队列接口适应"规范"操作集,您可以使其统一并与符合相同外部规范的其他基于类的优先级队列实现互换.

Answer 2

priority_queue（至少通常）是作为堆实现的。因此，真正的问题是priority_queue 是否提供您所需要的。当您使用 make_heap 时，您仍然可以访问所有元素。当您使用 priority_queue 时，您只有少数操作可以对元素进行非常有限的访问（基本上只是插入一个项目，然后删除队列头部的项目）。

Answer 3

C++11 标准

C++11 N3337 标准草案指定std::make_heap用于std::priority_queue在“23.6.4.1 priority_queue constructors”的构造函数中：

显式priority_queue

2 效果：用 x 初始化 comp 和用 y 初始化 c（复制构造或移动构造视情况而定）；调用 make_heap(c.begin(), c.end(), comp)。

和其他方法说：

void push(const value_type& x);

效果： c.push_back(x); push_heap(c.begin(), c.end(), comp)

然而，从较新的 n4724 开始，非构造函数方法的措辞变成了“好像”，所以我认为*_heap不能保证对方法的实际调用，只是它的功能行为。

所有这些都证实了/sf/answers/788659091/提到的关于std::priority_queue作为std::make_heap.

Step debug into g++6.4 stdlibc++ source 确认priority_queue转发到make_heap

在 Ubuntu 的 16.04 默认g++-6包或从源代码构建的GCC 6.4 上，您无需任何进一步设置即可进入 C++ 库。

使用它，我们可以很容易地确认这std::priority_queue只是一个std::make_heap带有底层的系列的包装器std::vector，这意味着性能将是相同的。

a.cpp：

#include <cassert>
#include <queue>

int main() {
    std::priority_queue<int> q;
    q.emplace(2);
    q.emplace(1);
    q.emplace(3);
    assert(q.top() == 3);
    q.pop();
    assert(q.top() == 2);
    q.pop();
    assert(q.top() == 1);
    q.pop();
}

编译和调试：

g++ -g -std=c++11 -O0 -o a.out ./a.cpp
gdb -ex 'start' -q --args a.out

现在，如果您std::priority_queue<int> q首先进入vector构造函数，它会进入构造函数，因此我们已经可以猜测std::priority_queue包含一个std::vector.

现在我们finish在 GDB 中运行以找到队列构造函数，然后再次进入，这将引导我们找到实际的队列构造函数/usr/include/c++/6/bits/stl_queue.h：

443       explicit
444       priority_queue(const _Compare& __x = _Compare(),
445              _Sequence&& __s = _Sequence())
446       : c(std::move(__s)), comp(__x)
447       { std::make_heap(c.begin(), c.end(), comp); }

这显然只是转发到对象的std::make_heap顶部c。

于是我们打开源文件vim，找到了c：

  template<typename _Tp, typename _Sequence = vector<_Tp>,
       typename _Compare  = less<typename _Sequence::value_type> >
    class priority_queue
    {

      [...]

      _Sequence  c;

所以我们得出结论，这c是一个vector.

如果我们进入其他方法，或者通过进一步检查源代码，我们很容易看到所有其他priority_queue方法也只是转发到std::make_heap函数系列。

选择堆 vs 平衡 BST 是有道理的，因为堆的平均插入时间更短，请参阅：堆 vs 二叉搜索树 (BST)