Better way to implement or feedback on this C# Max Heap Priority Queue

Question

Hi - 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 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

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.