22

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

4

5 回答 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在几个不同的容器上,包括您自己编写的一个。但一个setmap意味着不仅仅是一种排列数据的方式。

换句话说,标准容器不仅仅是其底层数据结构。

于 2010-06-30T18:12:09.810 回答
4

堆* 几乎总是使用数组作为底层数据结构来实现。因此,它可以被认为是一组对数组数据结构进行操作的算法。这是 STL 在实现堆时采用的路径 - 它适用于任何具有随机访问迭代器的数据结构(标准数组、向量、双端队列等)。

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

*特别是二进制堆。其他形式的堆(二项式、斐波那契等)不是。

于 2010-06-30T18:12:15.110 回答
1

好吧,堆并不是真正意义上的通用容器,与集合或映射具有相同的意义。通常,您使用堆来实现一些其他抽象数据类型。(最明显的是优先队列。)我怀疑这是不同处理的原因。

于 2010-06-30T18:06:30.863 回答