爲什麼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需要一個容器（默認情況下它是一個向量）。這實質上就是你的堆容器 - 它在你的底層數據結構上實現了一堆，併爲所有典型的堆操作提供了一個包裝容器。

*特別是二進制堆。其他形式的堆（二項式，斐波納契等）不是。