为什么C++中的堆实现为算法而不是容器？

Question

我想知道为什么堆概念实现为算法（make_heap,pop_heap, push_heap,sort_heap）而不是容器。我特别感兴趣的是某些人的解决方案也可以解释为什么set和map是容器而不是类似的算法集合（make_set add_set rm_set等）。

Answer 1

STL确实提供了std :: priority_queue形式的堆。 make_heap等功能在那里，因为它们在数据结构本身的领域之外使用（例如排序），并允许在定制结构之上构建堆（比如堆栈数组为“保持前10位”容器）。通过类推，你可以使用一个std :: set存储一个排序列表，或者你可以在std :: adjacent_find上使用std :: sort作为一个向量; std :: sort是更通用的，并且对底层数据结构做了很少的假设。

（作为一个说明，在std :: priority_queue实施实际上并没有提供它自己的存储;默认情况下它会创建一个std ::向量作为其后备存储）

Answer 2

那么，堆不是一个真正的通用容器，就像集合或地图一样。通常，您使用堆来实现其他抽象数据类型。 （最明显的是优先队列。）我怀疑这是不同治疗的原因。

Answer 3

一个明显的原因是你可以将元素排列成里面的另一个容器。
因此，您可以拨打make_heap()vector或deque甚至C数组。

Answer 4

堆是一个特定的数据结构。标准容器具有复杂性要求，但未指定如何实施。这是一个很好但很重要的区别。你可以在几个不同的容器上使用make_heap，包括你自己写的一个容器。但set或map不仅仅是一种安排数据的方式。

换句话说，标准容器不仅仅是它的基础数据结构。

Answer 5

堆*几乎总是使用数组作为基础数据结构实现的。因此，它可以被认为是对阵列数据结构进行操作的一组算法。这是STL在实现堆时所采用的路径 - 它可以用于任何具有随机访问迭代器（标准数组，矢量，双端队列等）的数据结构。

您还会注意到STL priority_queue需要一个容器（默认情况下它是一个向量）。这实质上就是你的堆容器 - 它在你的底层数据结构上实现了一堆，并为所有典型的堆操作提供了一个包装容器。

*特别是二进制堆。其他形式的堆（二项式，斐波纳契等）不是。