优先队列
2016-11-14 本文已影响0人
crf1028
优先队列（英语：Priority Queue）Wiki
</br>
特点
- 根据优先级提取数据
- 往往用链表实现
</br>
api及时间复杂度
| api | 作用 | 时间复杂度（普通） | 时间复杂度（二叉树） |
|---|---|---|---|
| insert | 插入数据 | O(1) | O(log n) |
| extract_max | 返回并删除队列内优先级最高数据 | O(n) | O(log n) |
| get_max | 返回队列内优先级最高数据 | O(1) | O(1) |
| len | 返回队列的长度 | O(1) | O(1) |
| is_empty | 返回队列是否为空 | O(1) | O(1) |
| delete | 删除数据 | O(n) | O(log n) |
</br>
实现
</br>
应用
- 戴克斯特拉算法（英语：Dijkstra's algorithm）
- 普里姆算法（英语：Prim's algorithm）
- 霍夫曼编码（英语：Huffman Coding）
- 堆排序（英语：Heapsort）
</br>
