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

Question

我想知道为什么堆概念被实现为算法(make_heap, pop_heap, push_heap, sort_heap)而不是容器。我特别感兴趣的是，有人的解决方案是否能够解释为什么set和map是容器，而不是类似于算法集合（make_set add_set rm_set 等）。

- KitsuneYMG

---

记录一下，有一个基于堆的容器：priority_queue。 - avakar

为什么不呢？对于堆，您可以使用任何随机访问序列。不强制使用特殊容器是好的。人们应该尝试解耦事物。不，使用序列并不适用于集合和映射。对于这些情况，使用实际的二叉树要容易得多。 - sellibitze

由于有些人似乎感到困惑：kts是指数据结构[http://en.wikipedia.org/wiki/Heap_(data_structure)]，而不是自由存储器。 - Dennis Zickefoose

因为你可以很容易地将底层容器作为模板参数，例如 heap<type, vector> h;。 - Inverse

@Inverse：我同意，这不会是唯一的容器适配器。 - Matthieu M.

Answer 1

STL提供了一个std::priority_queue形式的堆。make_heap等函数之所以存在，是因为它们在数据结构本身的领域之外也有用途（例如排序），并且允许在自定义结构上构建堆（例如“保留前10个”容器的堆栈数组）。

类比地，您可以使用std::set存储已排序的列表，或者使用带有std::adjacent_find的vector进行std::sort；std::sort更通用，并对底层数据结构做出了较少的假设。

（需要注意的是，std::priority_queue实现实际上并没有提供其自己的存储方式；默认情况下，它会创建一个std::vector作为其后备存储器。）

- user295691

Answer 2

一个明显的原因是你可以将元素作为堆放置在另一个容器中。
所以你可以在vector或者deque甚至C数组上调用make_heap()。

- shoosh

Answer 3

堆是一种特定的数据结构。标准容器有复杂度要求，但不指定它们如何实现。这是一个微妙但重要的区别。你可以在多个不同的容器上使用make_heap，包括你自己编写的容器。但是，set或map意味着不仅仅是一种排列数据的方式。

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

- Michael Kristofik

Answer 4

堆（Heaps）几乎总是使用数组作为底层数据结构进行实现。因此，可以将其视为在数组数据结构上操作的一组算法。STL实现堆时采取了这种方式 - 它将适用于具有随机访问迭代器（标准数组、向量、双端队列等）的任何数据结构。

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

*特别是二叉堆。其他形式的堆（二项式堆、斐波那契堆等）则不是。

- Niki Yoshiuchi

Answer 5

嗯，堆并不像集合或映射那样是一种通用容器。通常情况下，您使用堆来实现其他抽象数据类型（最明显的是优先队列）。我认为这就是不同处理方式的原因。

- Peter Ruderman