classe Mucchio in .NET

Question

Eventuali duplicati:
Fibonacci, Binary, or Binomial heap in c#?

C'è qualche classe come heap in .NET? Ho bisogno di una sorta di collezione da cui posso recuperare min. elemento. Voglio solo 3 metodi:

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

non è possibile usare lista ordinata perché ci chiavi deve essere unico, e io potrebbe avere diversi elementi identici.

Answer 1

È possibile utilizzare SortedList o SortedDictionary (vedere la discussione in basso) con una chiave personalizzata. Se hai usato un tipo con uguaglianza referenziale, ma potrebbe essere confrontato in base al valore che ti interessa, allora potrebbe funzionare.

Qualcosa di simile a questo:

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

Ecco un esempio di lavoro di utilizzare un SortedDictionary che ha binary-heap caratteristiche prestazionali:

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

Risultati:

Element conteggio: 100; Confronta conteggio per getMinElement: 0

Conteggio elementi: 100; Confronta count per deleteMinElement: 8

Conteggio elementi: 1000; Confronta conteggio per getMinElement: 0

Conteggio elementi: 1000; Confronta count per deleteMinElement: 10

Conteggio elementi: 10000; Confronta conteggio per getMinElement: 0

Conteggio elementi: 10000; Confronta count per deleteMinElement: 13

Conteggio elementi: 100000; Confronta conteggio per getMinElement: 0

Conteggio elementi: 100000; Confronta count per deleteMinElement: 14

Conteggio elementi: 1000000; Confronta conteggio per getMinElement: 0

Conteggio elementi: 1000000; Confronta contano deleteMinElement: code 21

Answer 2

priorità sembrano una buona misura per il vostro problema: Priority queue in .Net

Google per "code di C# di priorità" per ulteriori implementazioni.