Better way to implement or feedback on this C# Max Heap Priority Queue
been writing some data structures of late as a review for myself. I was wondering if anyone had some feedback on the code below, better, faster ways perhaps?
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using Micro开发者_如何学运维soft.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);
}
}
}
I'd make your PriorityItem an IComparable. You could then keep integer priorities, or you could go slightly more exotic:
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)
{
}
}
This would give you a very nice array of options to use the PriorityItem (use it where your Data is both data and comparer, or provide a custom comparable, or provide an int using PriorityItem ). This would make your MaxHeapify about half as long. It would also allow you to use a standard sorted backing store (like SortedList) which would remove the need for MaxHeapify altogether, though that would require your Priority property have a private setter.
精彩评论