什么是优先级队列
一个优先级队列是重要元素在最前面的队列。则个队列可能是max-priority queue（最大元素优先）或者一个min-priority queue（最小元素优先）。
为什么要用优先级队列呢？
优先级队列对于处理大量数据并且要不断重复的标识哪个是最重要的元素（最大元素优先或者最小元素优先）的算法非常有用。
几个得益于优先级队列的算法？
Event-driven simulations：每个事件有相应的时间戳，并且你希望事件按照你的时间戳顺序来执行。这个优先级队列让你很容易找到下一个需要执行的事件。
Dijkstra's algorithm（迪杰斯特拉算法）的图搜索使用一个优先队列来计算最低的成本。
Huffman coding 来数据压缩，他需要不断重复的找到具有最小频率的两个没有父节点的节点。
A*寻址
使用普通的队列或者普通的数组，需要不断反复的找到最大的元素。优先级队列针对它做了优化。
你可以用优先级队列做什么事情呢？
优先级队列常用的操作
进队：插入一个新的元素到队列
出队：删除并返回这个队列中最重要的元素
找到最大或者最小的元素：返回最大或者最小的元素但是不删除
改变优先级：决定队列中哪个元素更重要就是改变元素的优先级
怎么实现优先级队列
有很多方法实现优先级队列:
有序数组实现的方式：最重要的元素在数组最后面。缺点是插入新的元素很慢，因为插入要有序的插入。
二叉搜索树：这对于创建双端优先级队列非常有用，因为他可以很高效的找到最大或者最小元素。
堆的实现：堆本身就是一个优先级的天然结构。并且堆比有序数组更高效因为堆仅仅要求部分有序，堆的大部分操作都是O（logn）
苹果的也有优先级队列的实现 CFBinaryHeap
Demo：https://github.com/renmoqiqi/DSPriorityQueue
参考链接：https://github.com/ksco/swift-algorithm-club-cn/tree/master/Priority%20Queue
https://en.wikipedia.org/wiki/Priority_queue
网友评论