91超碰碰碰碰久久久久久综合_超碰av人澡人澡人澡人澡人掠_国产黄大片在线观看画质优化_txt小说免费全本

溫馨提示×

C#中PriorityQueue怎么實現

c#
小億
123
2023-12-22 03:13:03
欄目: 編程語言

在C#中,可以使用堆(Heap)來實現PriorityQueue。堆是一種特殊的二叉樹結構,滿足以下性質:

  1. 完全二叉樹:除了最后一層,其他層的節點數都是滿的,最后一層的節點都靠左排列。
  2. 堆序性:對于最大堆,父節點的值大于等于其子節點的值;對于最小堆,父節點的值小于等于其子節點的值。

在C#中,可以使用數組來表示堆。根據堆的性質,可以通過簡單的數學運算來找到節點的父節點和子節點。

下面是一個使用數組實現最小堆的PriorityQueue的示例代碼:

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;
    }
}

上述代碼中,我們使用了一個List來存儲堆的元素。Enqueue方法首先將元素添加到List的末尾,然后根據堆的性質進行上浮操作(HeapifyUp)。Dequeue方法首先將堆頂元素(即最小元素)取出,并將最后一個元素放到堆頂,然后根據堆的性質進行下沉操作(HeapifyDown)。

這樣,我們就實現了一個使用數組實現最小堆的PriorityQueue。可以根據需要修改代碼來實現最大堆或者自定義優先級的堆。

0
靖安县| 乌苏市| 洛扎县| 漳州市| 焦作市| 星座| 涟源市| 寻乌县| 昌黎县| 浮梁县| 澎湖县| 缙云县| 团风县| 韩城市| 卢龙县| 东海县| 安义县| 邵阳市| 咸宁市| 双峰县| 娄底市| 松原市| 阿城市| 五台县| 翼城县| 波密县| 青川县| 汝城县| 将乐县| 本溪市| 乃东县| 连江县| 正安县| 福州市| 安宁市| 上栗县| 六盘水市| 清苑县| 东明县| 车致| 福建省|