make_heap 有什么意义？
有人可以告诉我 STL 堆函数模板（如 std::make_heap）的要点吗？ 为什么有人会使用它们？ 有实际用途吗？
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?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（7）
它们用于构建和维护堆数据结构
They are used to construct and maintain the Heap data structure
算法和数据结构课程可以很好地回答你的直接问题。 堆在计算机科学的算法中随处可见。 引用下面链接的 make_heap 函数，“堆是一棵树，其中每个节点都链接到不大于其自身值的值。” 虽然堆有很多应用，但我最常使用的一个是在搜索问题中，当您想要有效地跟踪 N 个值的排序列表时。
当我第一次遇到 STL 堆函数时，我也有和你类似的困惑。 不过我的问题有点不同。 我想知道“为什么 STL 堆不与 std::vector 属于同一类数据结构？” 我认为它应该像这样工作：
STL 堆函数背后的想法是它们允许您从几个不同的底层 STL 容器（包括 std::vector）创建堆数据结构。 如果您想传递容器以在程序的其他地方使用，这非常有用。 这也有点好，因为如果您选择使用 std::vector 以外的东西，您可以选择堆的底层容器。 您真正需要的是以下内容：
这意味着您可以将许多不同的容器放入堆中 方法签名中的比较器也是可选的，您可以在 make_heap 的 STL 页面中阅读有关可以尝试的不同内容的更多信息功能。
链接：
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.
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:
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:
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.
Links:
除了上述之外，STL的排序算法是introsort，它是快速排序和排序的混合堆排序（如果前者表现不佳，它会从快速排序故障转移到堆排序）。 make_heap 创建一个堆结构，这是运行 heapsort 所需要的，也是 introsort 所需要的。
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.
std::make_heap在实践中几乎不应该使用。 虽然堆对于优先级队列确实很有用，但这并不能解释为什么您想要手动维护该结构。 如果您只需要一个优先级队列，std::priority_queue有一个更有用的接口。如果直接使用 make_heap 及其同级容器，则必须确保每次对底层容器进行更改时都使用它们。 我见过它们被使用过两三次，并且每一次都被错误地使用。
我自己只直接使用过一次堆操作，因为我需要使用向量作为优先级队列一段时间，然后对其进行排序。 您很可能永远不需要
std::make_heap。如果您需要一个能够更改元素的优先级队列，您可以使用
std::set。 您可以分别使用*s.begin()或*s.rbegin()获取最小或最大元素，并通过删除旧值并插入新值来更新元素一。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.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 time they were used incorrectly.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.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.如果你想从列表中创建一个优先级队列，那么，你可以使用制作堆：
If you want to make a priority queue out from a list, well, you can use make_heap:
您应该使用
std::make_heap()以及std::push_heap()和std::pop_heap()来维护向量或数组顶部的二叉堆； 后两个函数保持堆不变。 您还可以使用 std::heap_sort() 来对此类堆进行排序。 虽然您确实可以使用 std::priority_queue 作为优先级队列，但它不允许您了解其内部，而这也许是您想要的。 此外，std::make_heap()和std::heap_sort()一起构成了一种在 C++ 中进行堆排序的非常简单的方法。You are supposed to use
std::make_heap()along withstd::push_heap()andstd::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 usestd::heap_sort()to sort such a heap. While it is true that you could usestd::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()andstd::heap_sort()together make a very simple way of doing heapsort in C++.构造[二进制]堆本质上有两种方法：创建一个空堆并一次将每个元素插入其中，或者采用一系列值并将它们堆化。
堆上的每个推送操作都需要 O(logn) 时间，因此如果将 N 个项目推送到堆上，则需要 O(NlogN) 时间。 然而，从值数组构建二叉堆只需要 O(N) 时间。
因此，将每个元素插入到数组（或其他支持随机访问迭代器的容器）中，然后在数组上调用 make_heap() 比在插入时维护堆结构更有意义。
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.
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.