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

Question

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

Answer 1

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

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

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

Answer 2

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

Answer 3

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

你想继续阅读 二叉搜索树的。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)，因为您需要重新查找最小的元素（请记住 Big O 表示法是最坏的情况）。您还可以通过检查要删除的元素是否是（已知的）最小元素来进行优化，如果不是，则不要进行任何重新检查来查找最小元素。

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

Answer 6

哈普雷特：

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

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

Answer 7

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

但是，如果您只需要从前/后推入/弹出，则可以使用mindeque，它可以为所有操作（包括findmin）实现摊余常数时间。你可以做 scholar.google.com 搜索 了解有关此结构的更多信息。我和一位朋友最近合作开发了一个更容易理解和实现的 Mindeque 版本。如果这就是您正在寻找的内容，我可以为您发布详细信息。