更好的方式来实现或反馈这个C＃最大堆优先级队列

Question

最近写了一些数据结构作为自己的审查。我想知道是否有人对下面的代码有一些反馈，也许更好，更快的方法？

using System; 
using System.Collections.Generic; 
using System.Linq; 
using System.Text; 
using Microsoft.VisualStudio.TestTools.UnitTesting; 
namespace MaxHeapPriorityQueue 
{ 
    public class PriorityItem<T> 
    { 
     public T Data { get; set; } 
     public int Priority { get; set; } 
     public PriorityItem(T data, int priority) 
     { 
      Data = data; 
      Priority = priority; 
     } 

     public string ToString() 
     { 
      return Priority.ToString(); 
     } 
    } 

    public class PriorityQueue<T> 
    { 
     private List<PriorityItem<T>> array; 
     public PriorityQueue() 
     { 
      array = new List<PriorityItem<T>>(); 
     } 

     public void enqueue(T data, int priority) 
     { 
      PriorityItem<T> item = new PriorityItem<T>(data, priority); 
      array.Add(item); 
      MaxHeapify(); 
     } 

     public T dequeue() 
     { 
      T max = array[0].Data; 
      array.RemoveAt(0); 
      MaxHeapify(); 
      return max; 
     } 

     public void MaxHeapify() 
     { 
      //children must be less than the parent 
      //left = 2i-1 
      //right = 2i 
      for (int i = 0; i < array.Count; i++) 
      { 
       int leftPos = CalcLeft(i); 
       int rightPos = CalcRight(i); 
       int leftPriority = 0; 
       int rightPriority = 0; 

       if (leftPos !=-1) 
        leftPriority = array[leftPos].Priority; 

       if (rightPos !=-1) 
        rightPriority = array[rightPos].Priority; 

       //swap with parents where applicable 
       int highestPriority = 0; 
       if (leftPriority > array[i].Priority) 
       { 
        highestPriority = leftPriority; 
       } 
       else 
       if (rightPriority > array[i].Priority && rightPriority > leftPriority) 
       { 
        highestPriority = rightPriority; 
       } 

       //swap 
       PriorityItem<T> temp; 
       temp = array[i]; 
       if (highestPriority == leftPriority && leftPos != -1) 
       {      
        array[i] = array[leftPos]; 
        array[leftPos] = temp; 
       } 
       else if (highestPriority == rightPriority && rightPos!=-1) 
       { 
        array[i] = array[rightPos]; 
        array[rightPos] = temp; 
       } 
      } 

     } 

     int CalcLeft(int i) 
     { 
      i++; 
      if ((2 * i)-1 < array.Count) 
       return (2 * i) -1; 
      else 
       return -1; 
     } 

     int CalcRight(int i) 
     { 
      i++; 
      if ((2 * i) < array.Count) 
      { 
       return (2 * i); 
      } 
      else 
      { 
       return -1; 
      } 
     } 

    } 


    class Program 
    { 
     static void Main(string[] args) 
     { 
      PriorityQueue<string> pq = new PriorityQueue<string>(); 

      pq.enqueue("a", 1); 
      pq.enqueue("b", 2); 
      pq.enqueue("c", 4); 
      pq.enqueue("e", 5); 
      pq.enqueue("d", 3); 

      string val = pq.dequeue(); 
      Assert.AreEqual("e", val); 
      val = pq.dequeue(); 
      Assert.AreEqual("c", val); 
      val = pq.dequeue(); 
      Assert.AreEqual("d", val); 

      pq.enqueue("e", 10); 

      val = pq.dequeue(); 
      Assert.AreEqual("e", val); 
      val = pq.dequeue(); 
      Assert.AreEqual("b", val); 
      val = pq.dequeue(); 
      Assert.AreEqual("a", val); 

     } 
    } 
} 

Answer 1

我想让您的PriorityItem为IComparable。然后，您可以继续整数优先级，或者你可以去稍微更奇特：

public class PriorityItem<DataType, ComparerType> : IComparable<PriorityItem<DataType, ComparerType>> 
    where ComparerType : IComparable 
{ 
    public DataType Data { get; set; } 
    public ComparerType Priority { get; set; } 

    public PriorityItem(DataType data, ComparerType priority) 
    { 
     Data = data; 
     Priority = priority; 
    } 

    public string ToString() 
    { 
     return Priority.ToString(); 
    } 

    public int CompareTo(PriorityItem<DataType, ComparerType> other) 
    { 
     if (other == null) return 1; 
     return Priority.CompareTo(other.Priority); 
    } 

    public int CompareTo(object other) 
    { 
     return CompareTo(other as PriorityItem<DataType, ComparerType>); 
    } 
} 

public class PriorityItem<DataAndComparerType> : PriorityItem<DataAndComparerType, DataAndComparerType> 
    where ComparerType : IComparable 
{ 
    public PriorityItem(DataAndComparerType data) : base(data, data) 
    { 
    } 
} 

这会给你的选项非常好的阵列使用PriorityItem（使用数据所在的位置数据和比较器，或提供一个自定义比较，或使用PriorityItem提供一个int）。这会使MaxHeapify大约只有一半。它也允许你使用一个标准的排序后备存储（如SortedList），它将完全取消对MaxHeapify的需求，尽管这需要你的Priority属性有一个私有setter。