Possible Duplicate:
Fibonacci, Binary, or Binomial heap in c#?

Is there any class like heap in .NET? I need some kind of collection from which I can retrieve min. element. I just want 3 methods:

  • Add()
  • RemoveMinElement()
  • GetMinElement()

I can't use sorted list because there keys has to be unique, and I might have several identical elements.

7

2 Answers

You could use SortedList or a SortedDictionary (see discussion below) with a custom key. If you used a type with referential equality, but could be compared based on the value you care about, then this could work.

Something like this:

class HeapKey : IComparable<HeapKey> { public HeapKey(Guid id, Int32 value) { Id = id; Value = value; } public Guid Id { get; private set; } public Int32 Value { get; private set; } public int CompareTo(HeapKey other) { if (_enableCompareCount) { ++_compareCount; } if (other == null) { throw new ArgumentNullException("other"); } var result = Value.CompareTo(other.Value); return result == 0 ? Id.CompareTo(other.Id) : result; } }

Here is a working example of using a SortedDictionary which has binary-heap performance characteristics:

using System; using System.Collections.Generic; using System.Linq; namespace SortedDictionaryAsBinaryHeap { class Program { private static Boolean _enableCompareCount = false; private static Int32 _compareCount = 0; static void Main(string[] args) { var rnd = new Random(); for (int elementCount = 2; elementCount <= 6; elementCount++) { var keyValues = Enumerable.Range(0, (Int32)Math.Pow(10, elementCount)) .Select(i => new HeapKey(Guid.NewGuid(), rnd.Next(0, 10))) .ToDictionary(k => k); var heap = new SortedDictionary<HeapKey, HeapKey>(keyValues); _compareCount = 0; _enableCompareCount = true; var min = heap.First().Key; _enableCompareCount = false; Console.WriteLine("Element count: {0}; Compare count for getMinElement: {1}", (Int32)Math.Pow(10, elementCount), _compareCount); _compareCount = 0; _enableCompareCount = true; heap.Remove(min); _enableCompareCount = false; Console.WriteLine("Element count: {0}; Compare count for deleteMinElement: {1}", (Int32)Math.Pow(10, elementCount), _compareCount); } Console.ReadKey(); } private class HeapKey : IComparable<HeapKey> { public HeapKey(Guid id, Int32 value) { Id = id; Value = value; } public Guid Id { get; private set; } public Int32 Value { get; private set; } public int CompareTo(HeapKey other) { if (_enableCompareCount) { ++_compareCount; } if (other == null) { throw new ArgumentNullException("other"); } var result = Value.CompareTo(other.Value); return result == 0 ? Id.CompareTo(other.Id) : result; } } } }

Results:

Element count: 100; Compare count for getMinElement: 0

Element count: 100; Compare count for deleteMinElement: 8

Element count: 1000; Compare count for getMinElement: 0

Element count: 1000; Compare count for deleteMinElement: 10

Element count: 10000; Compare count for getMinElement: 0

Element count: 10000; Compare count for deleteMinElement: 13

Element count: 100000; Compare count for getMinElement: 0

Element count: 100000; Compare count for deleteMinElement: 14

Element count: 1000000; Compare count for getMinElement: 0

Element count: 1000000; Compare count for deleteMinElement: 21

17

Priority Queues look like a good fit to your problem: Priority queue in .Net

Google for "C# priority queues" for more implementations.

1