优先队列不再遵循先入先出的原则，分为两种情况：

1.最大优先队列，无论入队顺序如何，都是当前最大的元素优先出队；

2.最小优先队列，无论入队顺序如何，都是当前最小的元素优先出队；

优先队列的实现：

二叉堆的特性：

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

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

因此可以用最大堆实现最大优先队列，每一次入队就是堆的插入操作，出队就是删除堆顶节点。入队是先把值放到队列最后，再上浮；出队是删除堆顶元素，取队列最后一个值放堆顶，再下沉。

上沉和下浮时间复杂度都是O(logn)。

代码实现（二叉堆实现优先队列）：

using System;
using System.Collections.Generic;namespace CSharpTest01
{class PriorityQueue{private int[] array;private int size;public PriorityQueue(){// 初始长度32array = new int[32];}/// <summary>/// 入队/// </summary>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;}/// <summary>/// 上浮调整/// </summary>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;}/// <summary>/// 下沉调整/// </summary>public void DownAdjust(){// temp 保存父节点的值，用于最后的赋值int parentIndex = 0;int temp = array[parentIndex];int childIndex = 1;while (childIndex < size){// 如果有右孩子，且右孩子大于左孩子的值，则定位到右孩子if (childIndex + 1 < size && array[childIndex + 1] > array[childIndex]){childIndex++;}// 如果父节点大于任何一个孩子的值，直接跳出if (temp >= array[childIndex]){break;}array[parentIndex] = array[childIndex];parentIndex = childIndex;childIndex = 2 * childIndex + 1;}array[parentIndex] = temp;}/// <summary>/// 队列扩容/// </summary>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();}}
}