与编程问题有关：假设有一组可以相互比较和排序的对象。在添加对象和偶尔删除当前最小元素时，跟踪集合中最小元素的最有效方法是什么？

解决方案

回答

如果需要随机插入和删除，最好的方法可能是排序数组。插入和删除应为O(log(n))。

回答

使用最小堆是最好的方法。

http://zh.wikipedia.org/wiki/堆_(数据结构)

它是为此应用量身定制的。

回答

@哈普雷特
那不是最佳的。删除对象后，Erickson将不得不扫描整个集合以找到新的最小集合。

我们想阅读二进制搜索树的内容。 MS有一个很好的起点。但是，如果我们想深入研究，则可能需要一本类似《算法入门》(Cormen，Leiserson，Rivest，Stein)的书。

回答

If you need random insert and removal,
  the best way is probably a sorted
  array. Inserts and removals should be
  O(log(n)).

是的，但是我们需要对每个插入片段和(也许)每个删除进行重新排序，正如我们所说的那样，它们是O(log(n))。

使用Harpreet提出的解决方案：

• 我们在开始时进行了一次O(n)操作以找到最小的元素
• 此后的插入为O(1)(与已知的最小元素只需1个比较)
• deletes将是O(n)，因为我们将需要重新查找最小的元素(请记住，大O表示法是最坏的情况)。我们还可以通过检查要删除的元素是否是(已知)最小元素来进行优化，如果不是，则不要进行任何重新检查以找到最小元素。

因此，这取决于。这些算法中的一种对于删除次数少的大量插入的用例会更好，但另一种总体上更一致。我认为我会默认使用Harpreet的机制，除非我知道会经常删除最小的数目，因为这暴露了该算法的弱点。

回答

哈普雷特：

the inserts into that would be linear since you have to move items for an insert.

这不取决于集合的实现吗？如果它像一个链表那样工作，则插入将为O(1)，而如果像一个数组那样实现，则插入将是线性的，正如我们所说。

回答

取决于我们需要容器支持哪些操作。如果可能需要在任何给定时间删除min元素，则min-heap是最好的方法，尽管有几个操作是不平凡的(在某些情况下，摊销log(n)时间)。

但是，如果我们只需要从正面/背面进行推入/弹出操作，则只需使用一种思维方式即可为所有操作(包括findmin)实现摊销的固定时间。我们可以进行Scholar.google.com搜索以了解有关此结构的更多信息。最近，我和一个朋友合作，达成了一个更容易理解和实现的思维方式。如果这是我们想要的，我可以为我们发布详细信息。

回答

对于偶尔删除的斐波那契堆，甚至比最小堆还要快。插入为O(1)，找到最小值也为O(1)。删除为O(log(n))