鍦–#涓紝鍙互浣跨敤鍫嗭紙Heap锛夋潵瀹炵幇PriorityQueue銆傚爢鏄竴绉嶇壒娈婄殑浜屽弶鏍戠粨鏋勶紝婊¤冻浠ヤ笅鎬ц川锛?/p>

1. 瀹屽叏浜屽弶鏍戯細闄や簡鏈€鍚庝竴灞傦紝鍏朵粬灞傜殑鑺傜偣鏁伴兘鏄弧鐨勶紝鏈€鍚庝竴灞傜殑鑺傜偣閮介潬宸︽帓鍒椼€?/li>
2. 鍫嗗簭鎬э細瀵逛簬鏈€澶у爢锛岀埗鑺傜偣鐨勫€煎ぇ浜庣瓑浜庡叾瀛愯妭鐐圭殑鍊硷紱瀵逛簬鏈€灏忓爢锛岀埗鑺傜偣鐨勫€煎皬浜庣瓑浜庡叾瀛愯妭鐐圭殑鍊笺€?/li>

鍦–#涓紝鍙互浣跨敤鏁扮粍鏉ヨ〃绀哄爢銆傛牴鎹爢鐨勬€ц川锛屽彲浠ラ€氳繃绠€鍗曠殑鏁板杩愮畻鏉ユ壘鍒拌妭鐐圭殑鐖惰妭鐐瑰拰瀛愯妭鐐广€?/p>

涓嬮潰鏄竴涓娇鐢ㄦ暟缁勫疄鐜版渶灏忓爢鐨凱riorityQueue鐨勭ず渚嬩唬鐮侊細

public class PriorityQueue<T> where T : IComparable<T>
{
    private List<T> heap;

    public PriorityQueue()
    {
        heap = new List<T>();
    }

    public int Count => heap.Count;

    public void Enqueue(T item)
    {
        heap.Add(item);
        HeapifyUp(heap.Count - 1);
    }

    public T Dequeue()
    {
        if (heap.Count == 0)
        {
            throw new InvalidOperationException("PriorityQueue is empty");
        }

        T firstItem = heap[0];
        int lastIndex = heap.Count - 1;
        heap[0] = heap[lastIndex];
        heap.RemoveAt(lastIndex);
        HeapifyDown(0);

        return firstItem;
    }

    private void HeapifyUp(int index)
    {
        int parentIndex = (index - 1) / 2;

        while (index > 0 && heap[index].CompareTo(heap[parentIndex]) < 0)
        {
            Swap(index, parentIndex);
            index = parentIndex;
            parentIndex = (index - 1) / 2;
        }
    }

    private void HeapifyDown(int index)
    {
        int leftChildIndex = 2 * index + 1;
        int rightChildIndex = 2 * index + 2;
        int smallestChildIndex = index;

        if (leftChildIndex < heap.Count && heap[leftChildIndex].CompareTo(heap[smallestChildIndex]) < 0)
        {
            smallestChildIndex = leftChildIndex;
        }

        if (rightChildIndex < heap.Count && heap[rightChildIndex].CompareTo(heap[smallestChildIndex]) < 0)
        {
            smallestChildIndex = rightChildIndex;
        }

        if (smallestChildIndex != index)
        {
            Swap(index, smallestChildIndex);
            HeapifyDown(smallestChildIndex);
        }
    }

    private void Swap(int index1, int index2)
    {
        T temp = heap[index1];
        heap[index1] = heap[index2];
        heap[index2] = temp;
    }
}

涓婅堪浠ｇ爜涓紝鎴戜滑浣跨敤浜嗕竴涓狶ist鏉ュ瓨鍌ㄥ爢鐨勫厓绱犮€侲nqueue鏂规硶棣栧厛灏嗗厓绱犳坊鍔犲埌List鐨勬湯灏撅紝鐒跺悗鏍规嵁鍫嗙殑鎬ц川杩涜涓婃诞鎿嶄綔锛圚eapifyUp锛夈€侱equeue鏂规硶棣栧厛灏嗗爢椤跺厓绱狅紙鍗虫渶灏忓厓绱狅級鍙栧嚭锛屽苟灏嗘渶鍚庝竴涓厓绱犳斁鍒板爢椤讹紝鐒跺悗鏍规嵁鍫嗙殑鎬ц川杩涜涓嬫矇鎿嶄綔锛圚eapifyDown锛夈€?/p>

杩欐牱锛屾垜浠氨瀹炵幇浜嗕竴涓娇鐢ㄦ暟缁勫疄鐜版渶灏忓爢鐨凱riorityQueue銆傚彲浠ユ牴鎹渶瑕佷慨鏀逛唬鐮佹潵瀹炵幇鏈€澶у爢鎴栬€呰嚜瀹氫箟浼樺厛绾х殑鍫嗐€?/p>