How do I efficiently keep track of the smallest element in a collection?关于编程的问题:假设存在一组可以相互比较并排序的对象。在添加对象和偶尔删除当前最小元素时,跟踪集合中最小元素的最有效方法是什么? 使用最小堆是最好的方法。 http://en.wikipedia.org/wiki/Heap_data_structure 这是为此应用程序量身定制的。 偶尔删除斐波那契堆的速度甚至比最小堆快。插入为O(1),找到最小值也为O(1)。去除为O(log(n)) @Harpreet 您想在Binary搜索树上阅读。 MS有一个很好的起点。但是,如果您想深入研究,您可能想要一本类似算法入门的书(Cormen,Leiserson,Rivest,Stein)。 如果需要随机插入和移除,最好的方法可能是排序数组。插入和删除应为O(log(n))。 取决于您需要容器支持哪些操作。如果您可能需要在任何给定时间删除min元素,则min-heap是最好的方法,尽管有些操作是不重要的(在某些情况下,摊销log(n)时间)。 但是,如果您只需要从正面/背面进行推入/弹出操作,则可以使用一种思维方式,为所有操作(包括findmin)实现摊销固定时间。您可以进行Scholar.google.com搜索以了解有关此结构的更多信息。最近,我和一个朋友合作,达成了一个更容易理解和实现的思维方式。如果这是您要查找的内容,我可以为您发布详细信息。 Harpreet:
这不取决于集合的实现吗?如果它像一个链表那样工作,则插入将为O(1),而如果像一个数组那样实现,则插入将是线性的,正如您所说。
是的,但是您需要对每个插入片段和(也许)每个删除进行重新排序,正如您所说的那样,它是O(log(n))。 使用Harpreet提出的解决方案:
因此,这取决于。这些算法中的一种对于删除很少的大量插入用例会更好,但另一种总体上更一致。我认为我会默认使用Harpreet的机制,除非我知道会经常删除最小的数字,因为这暴露了该算法的弱点。 |