C++ make_heap 的意义是什么？

What is the point of make_heap?

提问by rlbond

Can someone please tell me the point of the STL heap function templates like std::make_heap? Why would anyone ever use them? Is there a practical use?

有人可以告诉我 STL 堆函数模板的要点std::make_heap吗？为什么会有人使用它们？有实际用途吗？

采纳答案by akappa

If you want to make a priority queueout from a list, well, you can use make_heap:

如果你想从列表中创建一个优先级队列，那么你可以使用 make_heap：

Internally, a heap is a tree where each node links to values not greater than its own value. In heaps generated by make_heap, the specific position of an element in the tree rather than being determined by memory-consuming links is determined by its absolute position in the sequence, with *first being always the highest value in the heap.

Heaps allow to add or remove elements from it in logarithmic time by using functions push_heap and pop_heap, which preserve its heap properties.

在内部，堆是一棵树，其中每个节点都链接到不大于其自身值的值。在由 make_heap 生成的堆中，一个元素在树中的具体位置而不是由消耗内存的链接决定，而是由它在序列中的绝对位置决定的，*first 始终是堆中的最高值。

堆允许通过使用函数 push_heap 和 pop_heap 在对数时间内添加或删除元素，这些函数保留其堆属性。

回答by James Thompson

Your direct question would be well-answered by a class in algorithms and data structures. Heaps are used all over the place in algorithms in computer science. To quote from the make_heap function linked below, "a heap is a tree where each node links to values not greater than its own value." While there are lots of applications for a heap, the one that I use most frequently is in search problems when you want to keep track of a sorted list of N values efficiently.

算法和数据结构课程可以很好地回答您的直接问题。堆在计算机科学的算法中无处不在。引用下面链接的 make_heap 函数，“堆是一棵树，其中每个节点都链接到不大于其自身值的值。” 虽然堆有很多应用程序，但我最常使用的应用程序是在搜索问题中，当您想有效地跟踪 N 值的排序列表时。

I had similar confusion to yours when I first encountered the STL heap functions. My question was a little bit different though. I wondered "Why isn't the STL heap in the same class of data structures as std::vector?" I thought that it should work like this:

当我第一次遇到 STL 堆函数时，我和你有类似的困惑。我的问题有点不同。我想知道“为什么 STL 堆与 std::vector 不在同一类数据结构中？” 我认为它应该像这样工作：

std::heap< int > my_heap;
my_heap.heap_insert( 7 );
my_heap.heap_insert( 3 );

The idea behind the STL heap functions though is that they allow you to make a heap data structure out of several different underlying STL containers, including std::vector. This can be really useful if you want to pass around the container for use elsewhere in your programs. It's also a little bit nice, because you can choose the underlying container of your heap if you so choose to use a something other than std::vector. All you really need are the following:

STL 堆函数背后的想法是，它们允许您从几个不同的底层 STL 容器（包括 std::vector）中创建一个堆数据结构。如果您想传递容器以在程序的其他地方使用，这可能非常有用。这也有点不错，因为如果您选择使用 std::vector 以外的其他内容，您可以选择堆的底层容器。您真正需要的是以下内容：

template <class RandomAccessIterator>
  void make_heap ( RandomAccessIterator first, RandomAccessIterator last );

This means that you can make lots of different containers into a heap A comparator is also optional in the method signature, you can read more about the different things that you can try in the STL pages for the make_heap function.

这意味着您可以将许多不同的容器制作成堆 方法签名中的比较器也是可选的，您可以在 make_heap 函数的 STL 页面中阅读有关可以尝试的不同内容的更多信息。

Links:

链接：

• Heap Data Structure
• make_heap function

• 堆数据结构
• make_heap 函数

回答by newacct

You are supposed to use std::make_heap()along with std::push_heap()and std::pop_heap()to maintain a binary heap on top of a vector or array; the latter two functions maintain the heap invariant. You can also use std::heap_sort()to sort such a heap. While it is true that you could use std::priority_queuefor a priority queue, it doesn't let you get at the insides of it, which perhaps you want to do. Also, std::make_heap()and std::heap_sort()together make a very simple way of doing heapsort in C++.

您应该std::make_heap()与向量或数组一起使用std::push_heap()并std::pop_heap()维护一个二元堆；后两个函数保持堆不变。您还可以使用std::heap_sort()对这样的堆进行排序。虽然您确实可以将其std::priority_queue用于优先级队列，但它并不能让您了解它的内部，而这可能是您想要的。此外，std::make_heap()和std::heap_sort()一起制作了一种在 C++ 中进行堆排序的非常简单的方法。

回答by J?rgen Fogh

std::make_heapshould almost never be used in practice. While it is true that heaps are useful for priority queues, that doesn't explain why you would want to manually maintain the structure. std::priority_queuehas a much more useful interface if all you need is a priority queue.

std::make_heap几乎不应该在实践中使用。虽然堆对优先队列很有用，但这并不能解释为什么您要手动维护结构。std::priority_queue如果您只需要一个优先级队列，则有一个更有用的界面。

If you use make_heapand its siblings directly, you have to make sure to use them every single time you make a change to the underlying container. I have seen them used two or three times and every single timethey were used incorrectly.

如果您make_heap直接使用及其兄弟，则必须确保每次对底层容器进行更改时都使用它们。我见过它们使用了两三次，每次都被错误地使用。

I have only used the heap operations directly once myself, because I needed to use a vector as a priority queue for a while and then sort it. You will most likely never need std::make_heap.

我自己只直接使用过一次堆操作，因为我需要使用一个vector作为优先级队列一段时间，然后对其进行排序。您很可能永远不需要std::make_heap.

If you need a priority queue with the ability to change elements, you can use std::set. You can get the smallest or largest element with *s.begin()or *s.rbegin()respectively and update an element by removing the old value and inserting the new one.

如果您需要能够更改元素的优先级队列，您可以使用std::set. 您可以分别使用*s.begin()或获取最小或最大元素，*s.rbegin()并通过删除旧值并插入新值来更新元素。

回答by Niki Yoshiuchi

There are essentially two ways to construct a [binary] heap: create an empty heap and insert each element into it one at a time, or take a range of values and heapify them.

构造[二进制]堆基本上有两种方法：创建一个空堆并将每个元素一次一个地插入其中，或者获取一系列值并将它们堆化。

Each push operation on a heap takes O(logn) time so if you are pushing N items onto a heap it will take O(NlogN) time. However to build a binary heap from an array of values takes only O(N) time.

堆上的每个推送操作都需要 O(logn) 时间，因此如果将 N 个项目推送到堆上，则需要 O(NlogN) 时间。然而，从一组值构建一个二进制堆只需要 O(N) 时间。

Thus it makes more sense to insert each element into an array (or other container that supports random access iterators) and then call make_heap() on the array than it does to maintain the heap structure while inserting.

因此，将每个元素插入数组（或其他支持随机访问迭代器的容器）然后在数组上调用 make_heap() 比在插入时维护堆结构更有意义。

回答by Todd Gardner

In addition to the above, the STL's sorting algorithm is introsort, which is a mixture of quicksort and heapsort (it fails over from quicksort to heapsort if the former is doing poorly). make_heap creates a heap structure, which is needed for running heapsort, which is needed for introsort.

除了上述之外，STL 的排序算法是introsort，它是快速排序和堆排序的混合（如果前者表现不佳，它将从快速排序故障转移到堆排序）。make_heap 创建了一个堆结构，运行 heapsort 需要它，introsort 需要它。

回答by Todd Gardner

They are used to construct and maintain the Heap data structure

它们用于构建和维护Heap 数据结构