今天简单介绍一下优先队列(priority queue, 以下简称PQ)这个数据结构的实现.
PQ又叫"堆"(heap), 但是可能优先队列这个名字更容易记忆它的用途: pq是一种队列, 不过不是先进先出(FIFO), 而是每次出队的元素永远是优先级最高的.
logical structure of PQ
个人感觉"堆"这个名字大概源于PQ的(逻辑上的)形状吧: PQ是一种树(tree), 准确的说, 是一种二叉树(binary tree), 说得再准确一点, 它是一种完全二叉树(complete binary tree): 没错, PQ是一种满足某些条件的完全二叉树.
所谓的"完全二叉树", 要满足:
- 除了最后一层, 所有层都排满(没有非空节点)
- 最后一层的所有非空节点都排在左边
一张图可以直观说明, 完全二叉树其实就是长得像这样:
一个完全二叉树能被成为PQ的话, 要满足的条件就是:
对于任何一个节点, 它的优先级都大于左右子节点的优先级.
比如下图 ...