data-structures - 如何有效地跟踪集合中的最小元素？

Question

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

Answer 1

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

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

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

Answer 2

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

Answer 3

@Harpreet
这不是最佳的。当一个对象被移除时，埃里克森将不得不扫描整个集合以找到新的最小的。

您想阅读二叉搜索树。MS 有一个很好的网站可以开始这条道路。但是如果你想深入研究，你可能想要一本像算法介绍（Cormen、Leiserson、Rivest、Stein）这样的书。

Answer 4

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

Answer 5

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

是的，但是您需要对每个插入和（也许）每个删除重新排序，正如您所说，这是 O(log(n))。

使用 Harpreet 提出的解决方案：

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

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

Answer 6

哈普雷特：

插入将是线性的，因为您必须为插入移动项目。

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

Answer 7

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

但是，如果您只需要从前/后推/弹出，您可以只使用一个能够为所有操作（包括 findmin）实现摊销恒定时间的 mindeque。您可以在 Academic.google.com 上进行搜索，以了解有关此结构的更多信息。我和一个朋友最近合作开发了一个更容易理解和实现的 Mindeque 版本。如果这是您要查找的内容，我可以为您发布详细信息。