C#实现优先队列算法

优先队列是一种特殊的数据结构，不遵循先进先出（FIFO）原则，而是根据元素的优先级进行出队操作。优先队列主要分为两种类型：

1. 最大优先队列：无论元素的入队顺序如何，总是将当前最大的元素优先出队。

2. 最小优先队列：无论元素的入队顺序如何，总是将当前最小的元素优先出队。

优先队列的实现：

优先队列通常使用二叉堆来实现。二叉堆具有以下特性：

1. 最大堆：堆顶元素是整个堆中的最大元素。

2. 最小堆：堆顶元素是整个堆中的最小元素。

因此，可以通过最大堆实现最大优先队列，通过最小堆实现最小优先队列。每次入队操作相当于在堆中插入一个元素，出队操作则是删除堆顶元素。入队时，新元素会被添加到堆的末尾，然后进行上浮操作；出队时，堆顶元素被删除，堆的最后一个元素被移到堆顶，然后进行下沉操作。上浮和下沉的时间复杂度均为O(log n)。

以下是使用C#实现的最大优先队列的代码示例：

using System;
using System.Collections.Generic;

namespace CSharpTest01
{
    class PriorityQueue
    {
        private int[] array;
        private int size;

        public PriorityQueue()
        {
            // 初始长度32
            array = new int[32];
        }

        /// 

        /// 入队
        /// 

        public void EnQueue(int key)
        {
            // 队列长度超出范围，扩容
            if (size >= array.Length)
            {
                Resize();
            }
            array[size++] = key;
            UpAdjust();
        }

        public int DeQueue()
        {
            if (size <= 0)
            {
                Console.WriteLine("the queue is empty!");
                return -1;
            }

            // 获取堆顶元素
            int head = array[0];

            // 让最后一个元素移动到堆顶
            array[0] = array[--size];
            DownAdjust();

            return head;
        }

        /// 

        /// 上浮调整
        /// 

        private void UpAdjust()
        {
            int childIndex = size - 1;
            int parentIndex = (childIndex - 1) / 2;

            // temp保存插入的叶子节点值，用于最后的赋值
            int temp = array[childIndex];

            while (childIndex > 0 && temp > array[parentIndex])
            {
                // 无须真正交换，单向赋值即可
                array[childIndex] = array[parentIndex];
                childIndex = parentIndex;
                parentIndex = parentIndex / 2;
            }
            array[childIndex] = temp;
        }

        /// 

        /// 下沉调整
        /// 

        public void DownAdjust()
        {
            // temp 保存父节点的值，用于最后的赋值
            int parentIndex = 0;
            int temp = array[parentIndex];
            int childIndex = 1;

            while (childIndex             {
                // 如果有右孩子，且右孩子大于左孩子的值，则定位到右孩子
                if (childIndex + 1  array[childIndex])
                {
                    childIndex++;
                }

                // 如果父节点大于任何一个孩子的值，直接跳出
                if (temp >= array[childIndex])
                {
                    break;
                }

                array[parentIndex] = array[childIndex];
                parentIndex = childIndex;
                childIndex = 2 * childIndex + 1;
            }
            array[parentIndex] = temp;
        }

        /// 

        /// 队列扩容
        /// 

        private void Resize()
        {
            // 队列容量翻倍
            int newSize = this.size * 2;
            int[] newArray = new int[newSize];
            Array.Copy(this.array, 0, newArray, 0, this.size);
            this.array = newArray;
        }
    }

    class Program
    {
        static void Main(string[] args)
        {
            PriorityQueue priorityQueue = new PriorityQueue();
            priorityQueue.EnQueue(3);
            priorityQueue.EnQueue(5);
            priorityQueue.EnQueue(10);
            priorityQueue.EnQueue(2);
            priorityQueue.EnQueue(7);
            Console.WriteLine(priorityQueue.DeQueue());
            Console.WriteLine(priorityQueue.DeQueue());
            Console.ReadLine();
        }
    }
}