数据结构与算法_优先队列

    普通队列(queue)是一种先进先出的数据结构，元素在队列尾追加，而从队列头删除。在优先队列中，元素被赋予优先级。当访问元素时，具有最高优先级的元素最先删除。

    优先队列（priority queue）具有最高级先出的行为特征。优先队列是0个或多个元素的集合，每个元素都有一个优先权或值，对优先队列执行的操作有1）查找；2）插入一个新元素；3)删除。在最小优先队列，查找操作用来搜索优先权最小的元素，删除操作用来删除该元素；对于最大优先队列，查找操作用来搜索优先权最大的元素，删除操作用来删除该元素。优先权队列中的元素可以有相同的优先权，查找与删除操作可根据任意优先权进行。

    在算法设计中，经常用到从序列中找一个最小值（或最大值）的操作，例如最短路径、哈夫曼编码等都需要找最小值。如果序列中顺序查找最小值（或最大值）需要O(n)的时间，而使用优先队列找最小值（或最大值）则只需要O(logn)的时间。

    优先队列是利用堆来实现的，堆可以看作一颗完全二叉树的顺序存储结构，在这棵完全二叉树中，如果每一个结点的值都大于等于左右孩子的值，则称为最大堆。如果每一个结点的值都小于等于左右孩子的值，称为最小堆。

    根据完全二叉树的性质，如果一个结点的下标为 i ,则其左孩子的下标为 2i, 其右孩子下标为2i+1，其双亲的下标为 i/2。且具有 n 个结点的完全二叉树的深度为[log2n] +1。

    普通的队列是先进先出的，而优先队列与普通队列不同，每次出队时按照优先级顺序出队。例如，最小值（或最大值）出队，优先队列中的记录存储满足堆的定义。优先队列除了构建初始堆之外，有出队和入队两种常用的操作。

算法步骤：

1）构建初始堆。

2）出队：堆顶出队，最后一个记录代替堆顶的位置，重新调整为堆。

3）入队：新记录放入最后一个记录之后，重新调整为堆。 

出队：调整堆的过程就是堆顶从根“下沉”到叶子的过程。

入队：入队后除了新入队记录之外，其他结点都满足最大堆的定义，只需要将新记录执行“上浮”操作，即可调整为堆。

代码实现：

算法分析：

优先队列是利用堆实现的一种特殊队列，堆是按照完全二叉树的逻辑来顺序存储的，具有 n 个结点的完全的二叉树的深度为 [log2n] +1。出队时，堆顶元素出队，最后一个元素代替堆顶，新的堆顶从根下沉到叶子，最多达到树的深度，时间复杂度为O(log n);入队时，新元素从叶子上浮到根，最多达到树的深度，时间复杂度也为 O(logn)。优先队列的入队和出队操作间复杂度均为 O(logn)，因此在n 个元素的优先队列中找一个最小值（或最大值）的时间复杂度为O(log n)。想找到一个最大值就是最大堆，找最小值就用最小堆。