高效的排序堆 [英] Efficient sorted heap

问题描述

我需要一个具有以下功能的数据结构：


1.快速访问最小元素。


2.快速插入新元素。


3.快速删除现有元素。


我一直在使用一个排序的不可变平衡二进制树集实现

，它在O（log n）中提供上述操作但在.NET上速度非常快，比OCaml慢大约8倍+ Linux。


我没有从使用不可变数据结构中受益，那么C＃程序员使用的是什么？b $ b可变数据结构？


-

飞蛙咨询有限公司Jon D Harrop博士
http://www.ffconsultancy.com/?u

推荐答案

SortedDictionary< ;是O（log n）的retreival，insert和removal;请参阅

" remarks"在这里：

http：// msdn.microsoft.com/en-us/library/f7fta44c.aspx


请注意，这只允许每个唯一键一个值。当然，你可以使用

SortedDictionary< Foo，List< Bar>（不理想）来制作一些看起来像ILookup<，>的球衣。 />

Marc

SortedDictionary<,is O(log n) for retreival, insert and removal; see
"remarks" here:

http://msdn.microsoft.com/en-us/library/f7fta44c.aspx

Note that this only allows one value per unique key. Of course, you
could always craft something grungy looking like ILookup<,>, using a
SortedDictionary<Foo, List<Bar>(not ideal).

Marc

嗨Marc


你知道这与Dictionary< T的区别吗？ ，Vinternally？我认为

基于哈希查找索引会比排序

键更快。如果你不知道OTTOYH我会花一些时间用反光板

:-)


-

Pete

====
http：//mrpmorris.blogspot。 com
http://www.capableobjects.com

Hi Marc

Do you know how this differs from Dictionary<T,Vinternally? I thought
that looking up an index based on a hash would be quicker than sorting the
keys. If you don''t know OTTOYH I will spend some time later with reflector
:-)

--
Pete
====
http://mrpmorris.blogspot.com
http://www.capableobjects.com

不是我的头脑;我必须检查反射器

或参考源符号服务器。


Marc

Not of the top of my head; I would have to check with either reflector
or the reference source symbol server.

Marc

这篇关于高效的排序堆的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！