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

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

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


推荐阅读

    Python之可迭代对象、迭代器、生成器

    Python之可迭代对象、迭代器、生成器,迭代,生成器,一、概念描述可迭代对象就是可以迭代的对象,我们可以通过内置的iter函数获取其迭代器,可

    应用程序对象

    应用程序对象,,应用程序对象是一个应用程序级对象,用于在所有用户之间共享信息,并且在Web应用程序运行期间可以保存数据。 应用的性质: 方法

    跟踪电脑意义|怎么追踪电脑

    跟踪电脑意义|怎么追踪电脑,,怎么追踪电脑  笔记本丢了,如果之前没有下载跟踪软件是不能找回来的,如果有下载的话就可以找回,但是要保证电

    Java创建对象的几种方式

    Java创建对象的几种方式,对象,方法,本文目录Java创建对象的几种方式java中几种创建对象的方式1Java中创建对象的集中方式有那些JAVA创建对

    5元素平板电脑上海维修|五元素平板

    5元素平板电脑上海维修|五元素平板,,五元素平板首先第一步:到自己平板官方网站下载你机子对应的固件包。常见平板的固件下载地址:昂达平板固