算法简单学习（十）—— 基于堆的优先级队列

2017-08-22 本文已影响54人刀客传奇

版本记录

版本号	时间
V1.0	2017.08.22

前言

将数据结构和算法比作计算机的基石毫不为过，追求程序的高效是每一个软件工程师的梦想。下面就是我对算法方面的基础知识理论与实践的总结。感兴趣的可以看上面几篇。
1. 算法简单学习（一）—— 前言
 2. 算法简单学习（二）—— 一个简单的插入排序
 3. 算法简单学习（三）—— 分治法与合并排序
 4. 算法简单学习（四）—— 冒泡排序
 5. 算法简单学习（五）—— 函数的增长
 6. 算法简单学习（六）—— 常用的几种相关函数
 7. 算法简单学习（七）—— 递归式
 8. 算法简单学习（八）—— 堆排序
 9. 算法简单学习（九）—— 建堆与堆排序算法

优先级队列

虽然堆排序算法是一个很漂亮的算法，但是实际中，快速排序的一个好的实现往往优于堆排序，下面我们要说的就是堆的一个很常见的应用：作为高效的优先级队列priority queue。队列分为两种：最大优先级队列和最小优先级队列，下面主要说的就是最大堆实现的最大优先级队列。

优先级队列是一种用来维护由一组元素构成的集合S的数据结构，这一组元素中的每一个都有一个关键字key，一个最大优先级队列支持下面操作：

INSERT(S, x)：把元素x插入集合S。这一操作还可以写作S ← S ∪ { x }。
MAXIMUM(S)：返回S中具有最大关键字的元素。
EXTRACT - MAX(S)：去掉并返回S中的具有最大关键字的元素。
INCREASE - KEY(S, x ,k)：将元素x的关键字的值增加到k，这里k值不能小于x原关键字的值。

优先级队列的应用

最大优先级队列应用

最大优先级队列的一个应用就是在一台分时计算机上进行作业调度，这种队列对要执行的各作业及它们之间的相对优先关系加以记录，当一个作业做完或者被中断时，用EXTRACT - MAX操作从所有等待的作业中，选择出具有最高优先级的作业，在任何时候，一个新作业都可以用INSERT加入到队列中。

最小优先级队列应用

最小优先级队列支持的操作包括INSERT、MINMUM、EXTRACT - MIN和DECREASE - KEY，这种队列可以用于基于事件驱动的模拟器中，在这种应用中，队列中的各项是要模拟的时间，每一个都有一个发生时间作为其关键字，事件模拟要按照各事件发生时间的顺序进行，因为模拟某一事件可能导致稍后对其他时间的模拟，模拟程序在每一步都使用EXTRACT - MIN来选择下一个模拟事件，当一个新事件产生时，使用INSERT将其放入队列中。

优先级队列的操作

优先级队列可以用堆来实现，通常我们需要在堆中的每个元素里存储对应的应用对象的柄（handle），在这里对象柄用数组下标表示，因为在堆操作过程中，堆元素会改变在数组中的位置，所以，在具体实现中，为了能够重新定位堆元素，我们需要更新应用中对象中的数组下标，这些对象柄需要被正确的维护。

下面就详细的讨论最大优先级队列的操作。

MAXIMUM操作

程序HEAP - MAXIMUM用Θ(1)时间实现了该操作。

HEAP - EXTRACT - MAX(A)操作

该程序实现了EXTRACT - MAX操作，它与HEAPSORT程序中的for循环体3 ~ 5 行很类似。

HEAP - INCREASE - KEY

它实现了 INCREASE - KEY的操作，在优先级队列中，关键字需要增加的元素由对应数组的下标 i 来标识，该过程首先将元素A [ i ]的关键字值更新为新的值，由于增加 A[ i ]的关键字可能会违反最大堆性质，所以过程中采用了类似INSERTION - SORT的插入循环的方式，在从本节点往根节点移动的路径上，为新增大的关键字寻找合适的位置，在移动的过程中，当元素的关键字小于其父母时，此时，最大堆性质成立，因此，程序终止。

下图是HEAP - INCREASE - KEY操作的一个示例，在n元堆上，HEAP - INCREASE - KEY的运行时间为O(lgn)。下面的MAX - HEAP - INSERT实现了INSERT操作，它的输入是要插入到最大堆A中的新元素的关键字，这个程序首先加入一个关键字值为 -∞ 的叶结点来扩展最大堆，然后调用HEAP - INCREASE - KEY来设置新结点的关键字的正确性，并保持最大堆性质。

在包含 n 个元素的堆上，MAX - HEAP - INSERT 的运行时间为 O(lgn)。