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

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））的