如何有效地追蹤集合中最小的元素？

Question

靜態編程問題：假設有一組對象可以相互比較並進行排序。隨着對象的添加和當前最小的偶爾刪除，追蹤集合中最小元素的最有效方法是什麼？

Answer 1

使用小堆是最好的方法。

http://en.wikipedia.org/wiki/Heap_(data_structure)

這是該應用程序量身定做的。

Answer 2

如果您需要隨機插入和刪除，最好的方法可能是一個排序的數組。插入和清除應該是O（log（n））。

Answer 3

@ Harpreet
這不是最優的。當一個對象被刪除時，erickson將不得不掃描整個集合來查找新的最小。

你想閱讀Binary search tree的。 MS有一個很好的site來啓動路徑。但是如果你想深入潛水，你可能想得到一本像Introduction to algorithms (Cormen, Leiserson, Rivest, Stein)這樣的書。

Answer 4

如果您需要隨機插入和移除， 最好的方法可能是排序的 數組。插入和清除應該是 O（log（n））。

是的，但是您需要重新對每個插入和每個刪除進行重新排序，並且（如您所述）是O（log（n））。

隨着由Harpreet提出的解決方案：

• 你有一個爲O（n）通過在開始尋找最小元件
• 插入件是O（1）之後（僅1相比需要對已知的最小元素）
• 刪除將是O（n），因爲您需要重新找到最小的元素（請記住Big O符號是最差的情況）。您還可以通過檢查以查看要刪除的元素是否是（已知的）最小元素來進行優化，如果不是，則不要執行任何重新檢查來查找最小元素。

所以，這取決於。其中一種算法對於刪除很少的插入大量用例會更好，但另一種算法總體上更加一致。我想我會默認使用Harpreet的機制，除非我知道最小的數字會經常被移除，因爲這暴露了算法中的一個弱點。

Answer 5

Harpreet：

的鑲入，這將是線性的，因爲你必須移動物品插入。

那不取決於集合的實現嗎？如果它的行爲像一個鏈表，插入將是O（1），而如果它像一個數組一樣實現，它將是線性的，如你所述。

Answer 6

取決於您需要容器支持哪些操作。A min-heap是最好的，如果你可能需要在任何給定的時間刪除最小元素，儘管幾個操作是不平凡的（在某些情況下分期log（n）時間）。但是，如果您只需要從前/後推/彈出，則可以使用mindeque來實現所有操作（包括findmin）的分攤恆定時間。你可以做a scholar.google.com search來了解更多關於這個結構。最近我和一個朋友合作，以達成一個更容易理解和實施的mindeque版本。如果這是你正在尋找的，我可以爲你發佈細節。

Answer 7

對於偶爾刪除Fibonacci Heap甚至比min-heap更快。插入是O（1），並且發現min也是O（1）。去除是O（日誌（n））的