关于数据结构：如何有效跟踪集合中的最小元素？

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

---

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

http://en.wikipedia.org/wiki/Heap_data_structure

这是为此应用程序量身定制的。

---

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

---

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

您想在Binary搜索树上阅读。 MS有一个很好的起点。但是，如果您想深入研究，您可能想要一本类似算法入门的书(Cormen，Leiserson，Rivest，Stein)。

---

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

---

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

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

---

Harpreet：

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

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

---

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的机制，除非我知道会经常删除最小的数字，因为这暴露了该算法的弱点。

---