Лучший способ реализовать или оставить отзыв об этой очереди приоритетов C # Max Heap

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 (используйте его, когда ваши Данные являются одновременно данными и компаратором, или предоставьте сопоставимый пользовательский объект, или предоставьте int с использованием PriorityItem). Это сделает ваш MaxHeapify примерно вдвое длиннее. Это также позволит вам использовать стандартное отсортированное хранилище резервных копий (например, SortedList), которое полностью устранит необходимость в MaxHeapify, хотя для этого потребуется, чтобы у свойства Priority был частный установщик.