优先级队列

优先级队列：队列中的元素带有优先级，元素按照优先级不同处于队列中的不同位置．

简单的 FIFO 队列，元素的位置与元素被加入进去时候的位置相同．优先级队列中，元素具有最高优先级（通常定义为具有最小的 key 值）的元素总是先从队列中出来．

使用场景：

• 任务调度: 操作系统中的进程调度就是使用优先级队列，有些进程优先级就是要高于其他进程（例如接电话优先级比玩游戏高）
• 排序： 我们将元素插入到一个 priority queue之后，元素在优先级队列里就已经是排好序的了(时间复杂度：　$O(n \log n)$)
• 使用在复杂的算法中：　比如 Dijksta’s Shortest path algorithm 算法中使用 priority queue 来保持没一个时刻的路径长度

支持的操作

所有的优先级队列都支持的操作：

• insert(e,k) : Insert a new element e with key k (插入一个优先级数值为key的元素e, key值越小优先级越大)
• remove-min: 删除并返回key值最小的元素(优先级最大，也就是在队首的元素)

特殊操作：

• Decrease-key(e, k）:减少优先级队列中 key 为 e 的元素的数值(减少量为 k 值)
• Increase-key(e, k）:增加优先级队列中 key 为 e 的元素的数值(增加量为 k 值)
• Delete(e): 在优先级队列中去掉 key　值为 e　的元素
• Find-min: 返回指向优先级队列中的最小值的指针

Decrease-key(e, k）常常被使用，比如迪杰斯特拉算法中需要经常使用，因为网络结点的权值一旦发生变化，那么就需要重新更新一边优先级队列

上面的几个操作是可以相互进行转换的：

• 如果给我们 Insert(e, k) 和　delete(e) 操作，我们可以通过这两个操作实现　increase-key　和　decrease-key　操作
• 如果给我们 increase-key　和　decrease-key　操作操作，我们可以通过这两个操作实现　delete(e) 操作
• 如果给我们 find-min　和　delete　操作操作，我们可以通过这两个操作实现　remove-min 操作
• 如果给我们 remove-min　和　insert　操作操作，我们可以通过这两个操作实现　find-min 操作