浅谈优先队列

优先队列也是一种队列，只不过不同的是，优先队列的出队顺序是按照优先级来的；在有些情况下，可能需要找到元素集合中的最小或者最大元素，可以利用优先队列ADT来完成操作，优先队列ADT是一种数据结构，它支持插入和删除最小值操作（返回并删除最小元素）或删除最大值操作（返回并删除最大元素）；

这些操作等价于队列的enQueue和deQueue操作，区别在于，对于优先队列，元素进入队列的顺序可能与其被操作的顺序不同，作业调度是优先队列的一个应用实例，它根据优先级的高低而不是先到先服务的方式来进行调度；

如果最小键值元素拥有最高的优先级，那么这种优先队列叫作升序优先队列（即总是先删除最小的元素），类似的，如果最大键值元素拥有最高的优先级，那么这种优先队列叫作降序优先队列（即总是先删除最大的元素）；由于这两种类型时对称的，所以只需要关注其中一种，如升序优先队列；

下面操作组成了优先队列的一个ADT；

1.优先队列的主要操作 优先队列是元素的容器，每个元素有一个相关的键值；

• insert(key, data)：插入键值为key的数据到优先队列中，元素以其key进行排序；
• deleteMin/deleteMax：删除并返回最小/最大键值的元素；
• getMinimum/getMaximum：返回最小/最大剑指的元素，但不删除它；

2.优先队列的辅助操作

• 第k最小/第k最大：返回优先队列中键值为第k个最小/最大的元素；
• 大小（size）：返回优先队列中的元素个数；
• 堆排序（Heap Sort）：基于键值的优先级将优先队列中的元素进行排序；

优先队列的应用

• 数据压缩：赫夫曼编码算法；
• 最短路径算法：Dijkstra算法；
• 最小生成树算法：Prim算法；
• 事件驱动仿真：顾客排队算法；
• 选择问题：查找第k个最小元素；
• 等等等等....

优先队列的实现比较

实现插入删除寻找最小值无序数组1nn无序链表1nn有序数组n11有序链表n11二叉搜索树logn(平均)logn(平均)logn(平均)平衡二叉搜索树lognlognlogn二叉堆lognlogn1

当然，优先队列不是三言两语就能够马上讲完的，更多情况下需要我们结合实际的例子来进行理解，这样学习起来才会更有效率，我们也可以到动力节点在线观看免费的视频课程，对自己的学习也有很大的提升。