Besserer Weg zur Implementierung oder Rückmeldung zu dieser C# Max-Heap-Prioritätswarteschlange

Question

Ich habe in letzter Zeit einige Datenstrukturen geschrieben, um mich selbst zu überprüfen. Ich frage mich, ob jemand Feedback zum untenstehenden Code hat, vielleicht bessere, schnellere Wege?

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using Microsoft.VisualStudio.TestTools.UnitTesting;
namespace MaxHeapPriorityQueue
{
    public class PriorityItem
    {
        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
    {
        private List> array;
        public PriorityQueue()
        {
            array = new List>();
        }

        public void enqueue(T data, int priority)
        {
            PriorityItem item = new PriorityItem(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 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 pq = new PriorityQueue();

            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

Ich würde Ihr PriorityItem zu einem IComparable machen. Sie könnten dann Ganzzahlprioritäten behalten, oder Sie könnten etwas exotischer werden:

public class PriorityItem : IComparable>
    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 other)
    {
        if (other == null) return 1;
        return Priority.CompareTo(other.Priority);
    }

    public int CompareTo(object other)
    {
        return CompareTo(other as PriorityItem);
    }
}

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

Dies würde Ihnen eine sehr schöne Auswahl an Optionen für die Verwendung des PriorityItem geben (verwenden Sie es, wenn Ihre Daten sowohl Daten als auch Vergleicher sind, oder geben Sie einen benutzerdefinierten Vergleicher an, oder geben Sie eine Ganzzahl mit PriorityItem an). Dadurch würde Ihr MaxHeapify etwa halb so lang werden. Es würde Ihnen auch ermöglichen, einen standardmäßig sortierten Back-End-Speicherplatz (wie SortedList) zu verwenden, was die Notwendigkeit von MaxHeapify vollständig entfernen würde, obwohl dies voraussetzen würde, dass Ihr Priority-Eigenschaft einen privaten Setter hat.