Efficient sorted heap

[Jon Harrop]

I need a data structure with the following capabilities:

1. Fast access to the smallest element.

2. Fast insertion of a new element.

3. Fast deletion of an existing element.

I have been using a sorted immutable balanced binary tree set implementation
that provides the above operations each in O(log n) but it is extremely
slow on .NET, around 8x slower than OCaml+Linux.

I do not benefit from the use of an immutable data structure, so what
mutable data structure would a C# programmer use?

--
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
http://www.ffconsultancy.com/?u

[Marc Gravell]

SortedDictionar y<,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
SortedDictionar y<Foo, List<Bar>(not ideal).

Marc

[Peter Morris]

Hi Marc

Do you know how this differs from Dictionary<T,Vi nternally? 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 Gravell]

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

Marc

[=?ISO-8859-1?Q?G=F6ran_Andersson?=]

Jon Harrop wrote:

I need a data structure with the following capabilities:

1. Fast access to the smallest element.

2. Fast insertion of a new element.

3. Fast deletion of an existing element.

I have been using a sorted immutable balanced binary tree set implementation
that provides the above operations each in O(log n) but it is extremely
slow on .NET, around 8x slower than OCaml+Linux.

I do not benefit from the use of an immutable data structure, so what
mutable data structure would a C# programmer use?

How often do you need to get the smallest element compared to how often
you insert and delete elements?

You could create a wrapper that contains a Dictionary<Key, Valuewith
all items, and a short array Key[] with a few of the smallest items,
that you keep sorted. When you insert an item, check if it should be
added to the array of smallest items, and when you delete an item, check
if it's in the array of smallest items.

If the array of smallest items happens to be empty when you try to
access the smallest item (i.e. you have deleted all of the smallest
items), you take a hit as you have to repopulate the array by looking
through the dictionary, otherwise it is an O(1) operation.

--
Göran Andersson
_____
http://www.guffa.com

[Peter Morris]

I can see that the hash could be more expensive for a key that is a long
string, but I wouldn't have thought many objects need such a complicated
hash do that? In my case there are no structs in my apps so mostely my keys
would be

enums
short strings
integers
instance of an object
I'd suspect in this case the Dictionary<T,Vw ould probably be quicker?

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

[not_a_commie]

I use a Binary Heap in my application. It is immediate (aka, O(1))
access to the smallest element. It is O(log n) to delete or insert an
element. Perhaps another type of heap (like a Soft Heap) would help
you. See the chart here: http://en.wikipedia.org/wiki/Fibonacci_heap.
I coded a Soft Heap in C# before. Unfortunately it does two
allocations per insert. This was significantly more expensive in
performance than my binary heap that stores everything in an array in
that lots of small allocations are expensive in C#. (The Binary Heap
changes the array size and copies when it runs out of room similar to
List<>).

[Jon Harrop]

Göran Andersson wrote:

Jon Harrop wrote:

>I need a data structure with the following capabilities:

1. Fast access to the smallest element.

2. Fast insertion of a new element.

3. Fast deletion of an existing element.

I have been using a sorted immutable balanced binary tree set
implementati on that provides the above operations each in O(log n) but it
is extremely slow on .NET, around 8x slower than OCaml+Linux.

I do not benefit from the use of an immutable data structure, so what
mutable data structure would a C# programmer use?

How often do you need to get the smallest element compared to how often
you insert and delete elements?

1 get smallest to 4 inserts and 2 removes.

You could create a wrapper that contains a Dictionary<Key, Valuewith
all items, and a short array Key[] with a few of the smallest items,
that you keep sorted. When you insert an item, check if it should be
added to the array of smallest items, and when you delete an item, check
if it's in the array of smallest items.

If the array of smallest items happens to be empty when you try to
access the smallest item (i.e. you have deleted all of the smallest
items), you take a hit as you have to repopulate the array by looking
through the dictionary, otherwise it is an O(1) operation.

That is O(n) instead of O(log n) though, so it is definitely slower for
sufficiently large problems.

--
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
http://www.ffconsultancy.com/?u

[Jon Harrop]

Marc Gravell wrote:

SortedDictionar y<,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
SortedDictionar y<Foo, List<Bar>(not ideal).

SortedDictionar y does not appear to provide the minimum element. Also, its
second type parameter is superfluous in this case, so it will probably
waste space.

--
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
http://www.ffconsultancy.com/?u

[Jon Harrop]

Peter Morris wrote:

Hi Marc

Do you know how this differs from Dictionary<T,Vi nternally?

SortedDictionar y is a balanced binary tree. This is essentially the
implementation I have been using but it is extremely slow on .NET.

I thought that looking up an index based on a hash would be quicker than
sorting the keys.

Only if you know the key you are looking for which I do not: I need the
smallest element. So hashing is obviously worse than useless here.

--
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
http://www.ffconsultancy.com/?u