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