我想知道为什么堆概念被实现为算法（make_heap, pop_heap, push_heap, sort_heap）而不是容器。我特别感兴趣的是一些人的解决方案也可以解释为什么set并且map是容器而不是类似的算法集合（make_set add_set rm_set 等）。
问问题
3594 次
5 回答
11
STL 确实以 std::priority_queue 的形式提供了一个堆。make_heap 等函数之所以存在，是因为它们在数据结构本身的领域之外使用（例如排序），并允许在自定义结构之上构建堆（例如用于“保持前 10 名”的堆栈数组）容器）。
以此类推，您可以使用 std::set 来存储排序列表，或者您可以使用 std::sort 在带有 std::adjacent_find 的向量上；std::sort 是更通用的，并且对底层数据结构几乎没有假设。
（注意，std::priority_queue 实现实际上并不提供自己的存储；默认情况下，它创建一个 std::vector 作为其后备存储。）
于 2010-06-30T18:24:15.867 回答
5
一个明显的原因是您可以将元素作为堆排列在另一个容器中。
所以你可以调用make_heap()一个vector或一个deque甚至一个 C 数组。
于 2010-06-30T18:08:55.837 回答
4
堆是一种特定的数据结构。标准容器具有复杂性要求，但未指定如何实现它们。这是一个很好但很重要的区别。您可以make_heap在几个不同的容器上，包括您自己编写的一个。但一个set或map意味着不仅仅是一种排列数据的方式。
换句话说，标准容器不仅仅是其底层数据结构。
于 2010-06-30T18:12:09.810 回答
4
堆* 几乎总是使用数组作为底层数据结构来实现。因此，它可以被认为是一组对数组数据结构进行操作的算法。这是 STL 在实现堆时采用的路径 - 它适用于任何具有随机访问迭代器的数据结构（标准数组、向量、双端队列等）。
您还会注意到 STL priority_queue 需要一个容器（默认情况下是一个向量）。这本质上是你的堆容器——它在你的底层数据结构上实现了一个堆，并为所有典型的堆操作提供了一个包装容器。
*特别是二进制堆。其他形式的堆（二项式、斐波那契等）不是。
于 2010-06-30T18:12:15.110 回答
1
好吧，堆并不是真正意义上的通用容器，与集合或映射具有相同的意义。通常，您使用堆来实现一些其他抽象数据类型。（最明显的是优先队列。）我怀疑这是不同处理的原因。
于 2010-06-30T18:06:30.863 回答