版本记录
| 版本号 | 时间 |
|---|---|
| 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)。
下面详细说一下HEAP - INCREASE - KEY的操作过程：
- a) 下标为 i 的结点以深阴影表示。
- b) 该结点将关键字的值增大道15。
- c) 经过
4 ~ 6行 while循环的一次迭代，该结点与其父节点交换了关键字，下标 i 上移到父亲结点。 - d) while循环的又一次迭代后的最大堆，此时，
A[PARENT(i)] ≥ A[ i ]，最大堆性质成立，程序终止。
后记
未完，待续~~~
