哪個更好找到最小元素堆棧或堆數據結構

Question

哪一個更好，實現一個堆棧來獲取最小元素或者維護一個堆數據結構來提取最小元素。兩者都給出了O（1）中的最小元素（如果實現了2堆棧，其中一個具有最小元素，另一個堆棧具有實際輸入）。

解釋我，在這情況下，我們可以使用堆棧或堆提取最小或最大的元素，爲什麼

Answer 1

你基本上可以使用a solution based on two stacks找到最小值，但它不是有效的（因爲它消耗2 * N內存，而堆消耗N內存）和堆棧應該被用於其他目的。

Answer 2

堆棧狀數據結構[1]和堆都支持「獲取最小」操作。 （請注意，我們正在討論堆數據結構，而不是用於內存分配的「堆」）。它們都允許添加新元素。

它們在去除元素方面有所不同。特別是，對於堆棧，您可以按照與插入相反的順序移除元素。使用堆，您可以按值排列元素（即始終刪除最小值）。

所以你應該使用支持你需要的操作的那個。

---

[1]所提到的數據結構是兩個平行的堆棧或一堆物品對;在這兩種情況下，堆棧都會保留這兩個項目，並將最小值保留到該點，這可以在O(1)中計算，因爲它只是推送的項目的最小值和之前的最小值。

Answer 3

MinHeaps旨在爲您提供極快的元素。只要偷看最小元素（不刪除）需要O（1）（常量）時間。通常，您將刪除最小元素，這將迫使您重新堆積堆，這需要log（n）時間。 wikipedia article圖形顯示MaxHeap，但實現MinHeap幾乎完全相同。

要找到一個（單）堆棧的最小元素需要ñ時間（和log（n）的< N），因爲你必須尋找堆棧中的所有元素，以找出最小。所以你需要每個元素關閉pop()，檢查它是否小於你記住的最小值，然後將它推到輔助棧上，直到你遍歷整個棧。因此，如果獲取最小元素是您數據結構的主要目的，您通常會希望使用MinHeap。另一方面，他人提到的雙堆棧解決方案對於操作（添加，移除和getMin）具有O（1）複雜性，但對於removeMin而言具有O（n）時間。在最壞的情況下它也有2N的空間要求。

總結：

   add/push 1 remove/pop 1 peekMin removeMin space 
       ========== ============ ======= ========= ===== 
one stack   O(1)   O(1)   O(n)  O(n)  n 
two stacks  O(1)   O(1)   O(1)  O(n)  2n 
minHeap   O(log(n)  N/A   O(1)  O(log n)  n 

作爲@rici指出minHeap，支持O（log n）的即removeMin操作，比疊層更快，但是，對於添加/刪除，並peekMin，雙堆棧溶液是比較快的。在關係「大於」和「小於」之外，minHeap也不維護秩序。

Answer 4

我真的不明白這個問題。

似乎類似的問題：我應該用錘子還是水罐？答案是：爲了什麼目的？

堆和棧的目的/行爲是不同。

堆提供API，如：插入（鍵X），GetandDeleteMin（）

雖然棧提供了一個LIFO（後進先出）API：推（X值），值pop（）方法（如果你想，GetMin（））。

你應該問自己的問題是，我需要一個支持min的LIFO結構嗎？如果是這樣，你可以使用堆棧。

OR

我需要一個「優先結構」在那裏我可以按隨機順序插入，取出一個最高/最低優先級？如果是這樣，你可以使用堆。

即你應該首先看你需要的行爲。

所有這些比較運行時間和空間使用情況的答案對我來說也是很奇怪的。當使用情況本質上不同時，甚至進行這種比較的意義何在？首先確定行爲，然後如果您有選擇，請將時間/空間等進行比較。

你真的在找什麼？