數據結構所需

Question

做一些思考我來，我需要支持的數據結構結束之後：

• 插入
• 刪除
• 查找
• 刪除最小

當然我想要以最好的複雜性來實現這一點。

我的想法是，一個自我平衡的二叉搜索樹將在O（log（n））（最糟糕的情況）中做A-D。 也許這可以以某種方式改進，所以A-C將在O（log（n））和D（我認爲會更頻繁）將在O（1）中運行。

我做了一個最糟糕的案例分析，但是如果你能想到一些會「快速」運行的東西，但它是攤銷分析還是平均分析比沒有問題。 任何改進，我想到的是歡迎！

（注：筆者認爲，A和d將更加頻繁的B和C）

Answer 1

它需要某種排序，平衡樹的。任何樹都不太可能更適合於最小刪除，因爲它仍然需要重新平衡。你要求的所有操作都是O（log（n））。紅黑樹隨時可以在C++和Java中使用。

Answer 2

你所描述的是一個priority queue，增加了一個「查找」操作。

它通常以min-heap的形式實施。您列出的所有操作（「查找」除外）都運行於O（日誌n），其中值得注意的是該作業的整體數據結構爲最高效的。值得注意的是，這是一個二叉樹的特例，與內存消耗和性能（同樣的漸近性能，但更好的常數因子）相比，它可以比一般的二叉搜索樹更有效地實現。

不幸的是，「查找」仍然需要O（n）。

它在Java中的PriorityQueue類中實現。