clase montón en .NET

Question

Duplicar posibles:
Fibonacci, Binary, or Binomial heap in c#?

¿Hay alguna clase como pila en .NET? Necesito algún tipo de colección de la cual pueda recuperar min. elemento. Sólo quiero 3 métodos:

• add()
• RemoveMinElement()
• GetMinElement()

que no puedo usar lista ordenada porque hay claves tiene que ser único, y yo podría tener varios elementos idénticos.

Answer 1

Puede usar SortedList o SortedDictionary (consulte la discusión a continuación) con una clave personalizada. Si usó un tipo con igualdad referencial, pero podría ser comparado en función del valor que le importa, entonces esto podría funcionar.

algo como esto:

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; 
    } 
} 

Aquí está un ejemplo de trabajo de utilizar un SortedDictionary que tiene características de rendimiento binario-montón:

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; 
      } 
     } 
    } 
} 

Resultados:

Element recuento: 100; Compare count para getMinElement: 0

Recuento de elementos: 100; Compare count para deleteMinElement: 8

Recuento de elementos: 1000; Compare count para getMinElement: 0

Recuento de elementos: 1000; Compare count para deleteMinElement: 10

Recuento de elementos: 10000; Compare count para getMinElement: 0

Recuento de elementos: 10000; Compare count para deleteMinElement: 13

Recuento de elementos: 100000; Compare count para getMinElement: 0

Recuento de elementos: 100000; Compare count para deleteMinElement: 14

Recuento de elementos: 1000000; Compare count para getMinElement: 0

Recuento de elementos: 1000000; Comparar cuentan para deleteMinElement: Colas 21

Answer 2

prioritarias ven como un buen ajuste a su problema: Priority queue in .Net

Google de "colas de C# prioritarios" para más implementaciones.