mirror of
https://git.wolves.top/wolves/leetcode.git
synced 2025-11-04 17:26:32 +08:00
16 lines
1.4 KiB
Markdown
16 lines
1.4 KiB
Markdown
# QUEUE
|
||
|
||
## PriorityQueue - 优先队列
|
||
|
||
- 优先队列也是一种队列，只不过不同的是，优先队列的出队顺序是按照优先级来的，可能需要找到元素集合中的最小或者最大元素，可以利用优先队列ADT来完成操作，优先队列ADT是一种数据结构，它支持插入和删除最小值操作（返回并删除最小元素）或删除最大值操作（返回并删除最大元素）；
|
||
|
||
- 这些操作等价于队列的`enQueue`和`deQueue`操作，区别在于，对于优先队列，元素进入队列的顺序可能与其被操作的顺序不同，作业调度是优先队列的一个应用实例，它根据优先级的高低而不是先到先服务的方式来进行调度；
|
||
- 如果最小键值元素拥有最高的优先级，那么这种优先队列叫作**升序优先队列**（即总是先删除最小的元素），类似的，如果最大键值元素拥有最高的优先级，那么这种优先队列叫作**降序优先队列**（即总是先删除最大的元素）；由于这两种类型时对称的，所以只需要关注其中一种，如升序优先队列；
|
||
- 优先队列的应用
|
||
- 数据压缩：赫夫曼编码算法；
|
||
- 最短路径算法：Dijkstra算法；
|
||
- 最小生成树算法：Prim算法；
|
||
- 事件驱动仿真：顾客排队算法；
|
||
- 选择问题：查找第k个最小元素；
|
||
- 等等等等....
|