何时应使用make_heap而不是优先队列？

Question

我有一个向量，想要用它来创建堆。我不确定是否应该使用C++的make_heap函数还是将我的向量放入优先队列中？就性能而言，哪个更好？在什么情况下应该使用其中之一？

- rolloff

---

如果你想要一个堆，那么你应该把它变成一个堆。优先队列并不都是堆。堆的性能往往更好。 - Wug

Answer 1

就性能而言，它们没有区别。 std::priority_queue 只是一个适配器类，将容器和堆相关的函数调用封装成一个类。这在 std::priority_queue 的规范中明确说明。

通过从公开的 std::vector 中构建一个 heap 并直接调用堆相关的函数，您使其对外部访问的可能性保持开放，这可能会损坏堆/队列的完整性。 std::priority_queue 充当障碍，将该访问限制为“规范化”的最小限度：push()、pop()、top() 等等。您可以将其视为实施自我约束的措施。

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

- AnT stands with Russia

Answer 2

C++11标准

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

explicit priority_queue

2 Effects: Initializes comp with x and c with y (copy constructing or move constructing as appropriate); calls make_heap(c.begin(), c.end(), comp).

其他方法如下：

void push(const value_type& x);

Effects: c.push_back(x); push_heap(c.begin(), c.end(), comp)

然而，在更新的n4724中，非构造函数方法的措辞变成了“as if”，因此我认为并不保证实际调用*_heap方法，只保证其功能行为。

所有这些都证实了https://dev59.com/Rmgu5IYBdhLWcg3wgnZh#11266558所提到的关于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，这意味着性能将是相同的。

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。

现在我们在 GDB 中运行 finish 来查找队列的构造函数，并再次进入，这将带领我们到实际的队列构造函数位于 /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); }

这 clearly 只是在 c 对象顶部转发到 std::make_heap。

因此，我们在 vim 中打开源代码文件并找到 c 的定义：

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

      [...]

      _Sequence  c;

因此我们得出结论，c是一个向量。

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

选择堆而不是平衡二叉搜索树等数据结构，是因为堆的平均插入时间更短，参见：Heap vs Binary Search Tree (BST)

- Ciro Santilli OurBigBook.com

---

哇！这是一个很棒的答案。清晰地详细解释了手头的问题。+1，但读作+10。 - Manohar Reddy Poreddy

Answer 3

优先队列（priority_queue）通常实现为堆。因此，真正的问题是优先队列是否提供了您所需的功能。当您使用make_heap时，仍然可以访问所有元素。当您使用priority_queue时，只有几个操作可以极其有限地访问元素（基本上只能插入一个项目，并删除队列头部的项目）。

- Jerry Coffin

Answer 4

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

例如，每当您向vector中推入新值时，应调用push_heap以扩展被视为堆的范围。如果您不使用priority_queue，则可以将vector的一半视为堆（std::make_heap(v.begin(), v.begin()+(v.size() / 2))），而另一半则按原样处理。

当您在priority_queue上调用push时，它会将一个新元素推送到底层容器的末尾，并调用push_heap以保持堆属性优先级（只有第一个元素最大才重要）。

我认为您应该考虑解决方案的设计和您的具体需求，而不是性能问题。

- Oleg

Answer 5

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

- JayS

---

它如何帮助进行原地合并？我认为，如果它继续使用从堆中提取操作，它将本质上成为堆排序，具有相应的速度和缺乏稳定性。 - Bulat

@Bulat 使用归并排序的堆在与堆排序相比有优势，例如对外部存储进行排序。它不是稳定排序，但我们并不总是需要这个特性。 - JayS

Answer 6

如果您不想修改那个向量，那么应该使用优先队列，因为它会创建一个单独的向量。但是，如果您可以编辑它，那么显然使用make_heap会更好，因为它不会创建辅助空间并会就地修改该向量，并因此节省空间。此外，优先队列易于实现。例如，当您在弹出元素时使用 make_heap 时，您必须使用两个命令，首先是pop_heap，然后是pop_back.. 但是在优先队列中，在推元素到堆中时也可以只使用一个命令。

现在，两者的性能将相同，因为优先队列不是容器，它使用一些底层容器比如 vector 或 deque ，它们使用与 make_heap 操作相同的堆操作。因此，应根据您的要求选择其中一个。

- shiwang