43

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

4

6 回答 6

46

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

通过直接heap从暴露的std::vector和调用堆相关的函数构建一个，您可以保持它对外部访问的可能性保持开放，这可能会破坏堆/队列的完整性。std::priority_queue充当限制访问“规范”最小值的障碍：push(),pop()等top()。您可以将其视为自律执行措施。

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

于 2012-06-29T17:47:04.433 回答
8

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

于 2012-06-29T17:47:20.780 回答
6

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)。

和其他方法说：

无效推送（常量值类型& x）；

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

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

所有这些都证实了https://stackoverflow.com/a/11266558/895245提到std::priority_queue的关于std::make_heap.

逐步调试到g++6.4 stdlibc++ 源以确认priority_queue转发到make_heap

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

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

一个.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函数族。

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

于 2018-08-21T09:23:30.347 回答
2

priority_queue不是容器。它是一个容器适配器，它使用特定的底层容器，例如vectoror deque，并提供一组特定的方法来处理数据。此外，它的实现依赖于*_heap算法。

例如，每当您将新值推送到 时，vector您都应该调用push_heap以扩展被视为堆的范围。如果你不使用priority_queue，它可以让你考虑，比如说，一半的vector堆（std::make_heap(v.begin(), v.begin() + (v.size() / 2))），而另一半将保持原样。

priority_queue当你调用它时会做什么push：它将一个新元素推到底层容器的后面并调用push_heap以保持堆属性的优先级（只关心第一个元素是最大的）。

我会说您最好考虑解决方案设计和您的具体要求，而不是性能问题。

于 2012-06-29T19:01:39.330 回答
0

如果您不想修改该向量，那么您应该使用priority queue它，因为它会创建一个单独的向量。但是，如果您有能力编辑它，那么显然使用make_heap会更好，因为它不会创建辅助空间并就地修改该向量，因此可以节省空间。此外，优先队列很容易实现。例如，当您在弹出元素时使用 make_heap 时，您必须先使用两个命令，pop_heap然后是pop_back.. 但在优先级队列的情况下，您可以只使用一个命令来完成。同样，同时将元素推入堆中。

现在，两者的性能是相同的，因为优先级队列不是容器，它使用一些底层容器作为向量或双端队列，它们使用与 make_heap 操作相同的堆操作。所以，你应该根据你的要求使用一个。

于 2018-02-04T11:09:39.727 回答
0

make_heap 以封装为代价提供了灵活性，例如，打印出堆。

make_heap 的一个有趣用途是就地合并排序，它在合并的一侧使用 make_heap，以实现 n/2(log(n/2)) 的最坏情况就地合并。

此示例显示了输入向量的使用并打印出创建的堆：

#include <queue>
#include <iostream>
#include <string>
#include <vector>
using namespace std;

void print(string prefix,vector<int>& v)
{
  cout << prefix;
  for(int i : v)
     cout << i << " ";
  cout << endl;
}

int main()
{
  vector<int> v={1,2,9,0,3,8,4,7,1,2,9,0,3,8,4,7};
  typedef priority_queue< int,vector<int>,greater<int> > MinQ;
  MinQ minQ(v.begin(),v.end()); //minQ
  print("After priority_queue constructor: ",v);

  make_heap(v.begin(),v.end(),greater<int>());
  print("After make_heap: ", v);
  return 0;
}

输出：

After priority_queue constructor: 1 2 9 0 3 8 4 7 1 2 9 0 3 8 4 7
After make_heap: 0 1 0 1 2 3 4 7 2 3 9 8 9 8 4 7
于 2018-07-28T05:01:48.703 回答