为什么堆在 c++ 中？作为算法而不是容器来实现？
我想知道为什么堆概念是作为算法实现的（make_heap、pop_heap、push_heap、sort_heap）而不是一个容器。我特别感兴趣的是，某些人的解决方案也可以解释为什么 set 和 map 是容器而不是类似的算法集合（make_set add_set rm_set 等）。
I was wondering why the heap concept is implemented as algorithms (make_heap, pop_heap, push_heap, sort_heap) instead of a container. I am especially interested is some one's solution can also explain why set and map are containers instead of similar collections of algorithms (make_set add_set rm_set etc).
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（5）
STL 确实提供了 std::priority_queue 形式的堆。 make_heap 等函数之所以存在，是因为它们在数据结构本身的领域之外使用（例如排序），并且允许在自定义结构之上构建堆（例如用于“保留前 10 个”的堆栈数组）容器）。
以此类推，您可以使用 std::set 来存储排序列表，也可以使用 std::sort 对带有 std::adjacent_find 的向量进行排序； std::sort 是更通用的，并且对底层数据结构做出很少的假设。
（需要注意的是， std::priority_queue 实现实际上并不提供自己的存储；默认情况下，它创建一个 std::vector 作为其后备存储。）
STL does provide a heap in the form of a std::priority_queue. The make_heap, etc., functions are there because they have uses outside the realm of the data structure itself (e.g. sorting), and to allow heaps to be built on top of custom structures (like stack arrays for a "keep the top 10" container).
By analogy, you can use a std::set to store a sorted list, or you can use std::sort on a vector with std::adjacent_find; std::sort is the more general-purpose and makes few assumptions about the underlying data structure.
(As a note, the std::priority_queue implementation does not actually provide for its own storage; by default it creates a std::vector as its backing store.)
一个明显的原因是您可以将元素排列为堆内部另一个容器。
因此，您可以在
vector或deque甚至 C 数组上调用make_heap()。One obvious reason is that you can arrange elements as a heap inside another container.
So you can call
make_heap()on avectoror adequeor even a C array.堆是一种特定的数据结构。标准容器有复杂性要求，但没有指定它们如何实现。这是一个很好但很重要的区别。您可以在几个不同的容器上
make_heap，包括您自己编写的容器。但是set或map不仅仅意味着一种排列数据的方式。换句话说，标准容器不仅仅是其底层数据结构。
A heap is a specific data structure. The standard containers have complexity requirements but don't specify how they are to be implemented. It's a fine but important distinction. You can
make_heapon several different containers, including one you wrote yourself. But asetormapmean more than just a way of arranging the data.Said another way, a standard container is more than just its underlying data structure.
堆* 几乎总是使用数组作为底层数据结构来实现。因此，它可以被认为是一组对数组数据结构进行操作的算法。这是 STL 在实现堆时所采用的路径 - 它适用于任何具有随机访问迭代器的数据结构（标准数组、向量、双端队列等）。
您还会注意到，STLpriority_queue 需要一个容器（默认情况下是一个向量）。这本质上是您的堆容器 - 它在底层数据结构上实现堆，并为所有典型的堆操作提供包装容器。
*特别是二进制堆。其他形式的堆（二项式、斐波那契等）则不然。
Heaps* are almost always implemented using an array as the underlying data structure. As such it can be considered a set of algorithms that operate on the array data structure. This is the path that the STL took when implementing the heap - it will work on any data structure that has random access iterators (a standard array, vector, deque, etc).
You'll also notice that the STL priority_queue requires a container (which by default is a vector). This is essentially your heap container - it implements a heap on your underlying data structure and provides a wrapper container for all of the typical heap operations.
*Binary heaps in particular. Other forms of heaps (Binomial, Fibonacci, etc) are not.
嗯，堆实际上并不是与集合或映射相同意义上的通用容器。通常，您使用堆来实现一些其他抽象数据类型。 （最明显的是优先级队列。）我怀疑这就是不同处理的原因。
Well, heaps aren't really a generic container in the same sense as a set or a map. Usually, you use a heap to implement some other abstract data type. (The most obvious being a priority queue.) I suspect this is the reason for the different treatment.