在多用户环境中, 操作系统调度程序必须决定在若干进程中运行那个进程. 一般一个进程只能被允许运用一个固定的时间片. 一种算法是使用一个队列. 开始时作业被放在队列的末尾. 调度程度将反复提取队列中的第一个作业并运行它, 直到运行完毕或者该作业的时间片被用完, 并在作业为被用完时将其放入队列的末尾. 但是一般来说, 短的作业要尽可能快地结束, 这一点很重要, 因此在已经被运行的作业中这些短作业应该拥有优先权. 此外, 有些作业虽然短小但也很重要, 也应该拥有优先权. 这种特殊的应用似乎需要一些特殊的队列, 我们称之为优先队列.
模型
优先队列应该允许至少下面的两种操作, Insert(插入), 以及 DeleteMin(删除最小值), 它的作用是找出, 返回和删除优先队列中的最小值. Insert 操作相当于队列的入队, DeleteMin 操作相当于队列中的出队操作. 在贪婪算法中, 优先队列也是重要的, 因为该算法通过反复的求出最小元来进行计算.
一些简单的实现
使用简单链表可以在表头进行插入并以 O(1)的时间复杂度, 但是遍历最小元的话则需要 O(N)的时间复杂度. 另外的一种思路是始终保持排序状态, 这使得插入的高昂代价 O(N), 而 DeleteMin 的代价是 O(1), 但是在实际中, DeleteMin 的操作次数从不多于插入的操作次数.
还可以使用二叉查找树来实现优先队列, 它对这两种操作的时间都是 O(logN). 反复出去左子树的节点似乎损害树的平衡, 使得右子树加重, 最坏的情况下, 左子树为空, 右子树拥有的元素最多也就是它的两倍, 这只是在其期望深度上加上了一个小的常数.
使用查找树可能有些过分, 因为它支持的操作太多了实际上并不需要你这么多. 我们使用的数据结构不需要指针, 它以最坏的情形时间 O(logN)支持上述的两种操作, 插入实际上将花费常数平均时间, 并且能够使用线性的时间建立具有 N 项的优先队列.
二叉堆
二叉堆, 它的使用对于优先队列的实现是如此的普遍, 以至于堆可以不加修饰使用一般是指这种数据结构的实现. 和二叉查找树相类似, 堆也有两个性质, 即结构性和堆序性, 堆的操作必须必须要到堆的所有性质被满足时才能终止.
结构性质
堆是一棵被完全填满的二叉树, 有可能的例外只在底层, 在底层从左到右的填入, 这样的树称为完全二叉树. 容易证明, 一棵高为 h 的完全二叉树有 2^h 到 2^(h+1) - 1 个节点. 这意味着, 完全二叉树的高是 logN, 显然它是 O(logN).
一个很重要的规律是完全二叉树是不需要指针的, 它能够使用一个数组表示而不需要指针. 对于数组中的任意的位置 i 上面的元素, 其左儿子在位置 2i 上, 右儿子在左儿子后的单元 (2i+1) 中, 它的父亲则在位置 [i/2] 上. 因此, 这里面不需要指针, 而且遍历该树的操作也是非常简单. 这种实现的唯一问题在于需要事先确定堆的大小.
一个堆数据结构将由一个数组, 一个代表最大值的整数以及当前堆的大小组成. 下面是典型的有限队列的声明:
- struct HeapStruct;
- typedef struct HeapStruct *PriorityQueue;
- struct HeapStruct{
- int Capacity;
- int Size;
- ElementType *Element;
- }
堆序性质
使操作被快速执行的性质是堆序性, 由于我们想要找出最小元, 因此最小元应该在根上面, 那么我们考虑任意子树也是一个堆, 这任意节点就应该小于它的所有后裔.
由此, 我们得到了堆序的性质. 在一个堆中, 对于每个节点 X,X 的父亲中的关键字小于 X 中的关键字, 根节点除外. 在例子中, 我们假设关键字是整数, 虽然可能任意复杂.
根据堆序的性质, 最小元总是在根处能够找到, 因而 FindMin 可以以常数时间完成.
- PriorityQueue
- Initialize(int MaxElements){
- PriorityQueue H;
- if(MaxElements <MinPQSize){
- Error("queue is too small");
- }
- H = malloc(sizeof(struct HeapStruct));
- if(H == NULL){
- FatalError("out of space");
- }
- H->Elements = malloc((MaxElements + 1) * sizeof(ElementType));
- if(H->Elements == NULL){
- FatalError("out of space");
- }
- H->Capacity = MaxElements;
- H->Size = 0;
- H->Elements[0] = MinData;
- return H;
- }
基本的堆序操作
无论从概念上还是实际考虑, 执行插入和删除最小元都需要保持堆序性.
Insert(插入)
为了将 X 插入到空穴中, 我们在下一个空闲位置创建一个空穴, 否则该堆将不再是完全二叉树. 如果 X 可以放在空穴并不会破坏堆序性, 那么插入完成. 否则, 我们把父节点上面的元素移入空穴, 空穴就朝着根的方向上行了一步. 继续改过程, 知道空穴能够放下 X 为止.
这种一般的策略叫做上虑, 新元素在堆上虑直到找到正确的位置.
插入到一个二叉堆的过程:
- void
- Inserti(Element X, PriorityQueue H){
- int i;
- if(IsFull(H)){
- Error("Priority queue is full");
- return;
- }
- for(i = ++H->Size; H->Element[i/2]> X; i = i / 2){
- H->Elements[i] = H->Emelemts[i/2];
- }
- H->Elements[i] = X;
- }
在实现过程中, 我们总可以通过进行反复交换来进行实现, 这样就需要 3 条赋值语句, 那么上虑 d 层的话, 交换的次数就需要 3d, 而在这里仅仅需要 d+1 次.
如果要插入的元素是性的最小值, 那么它将一直被推导顶端. 在某一次时, i 将是 1, 我们就需要跳出循环, 故我们可以在 0 位置处放置一个很小的值, 来使循环终止, 这个值需要小于堆中的任何值, 我们称之为标记.
如果新插入的元素是新的最小元, 那么这种高度是 O(logN). 但是平均来看, 执行一次插入平均需要 2.607 次比较, 因此 Insert 将元素平均上移 1.607 层.
DeleteMin(删除最小元)
DeleteMin 以类似于插入的方式处理. 找出最小元是容易的, 问题的关键在于删除它. 当我们要要删除一个最小元时, 在根节点产生了一个空穴. 由于现在堆缺少了一个元素, 因此堆中的最后一个元素 X 必须要移动到该堆的某个地方. 如果 X 可以被放到空穴中, 那么 DeleteMin 就完成了. 我们的做法是将空穴两个儿子中的较小者移入空穴, 这样就能够把空穴向下推进, 重复该步骤直到 X 可以放在该空穴中. 综上, 我们的做法是将 X 放置在从根开始包含最小儿子的一条路径上面的正确的位置. 我们将这种策略叫做下虑, 并且也可以通过覆盖来避免交换, 下面是下虑的过程示意图:
在堆中经常发生的错误是当堆中存在偶数个元素的时候, 此时将遇到一个节点只有一个儿子的情况, 所以我们必须要考虑节点只有一个儿子的情况, 当堆的元素个数是偶数的时候, 在每个开始下虑的时候, 可将其值大于堆中任何元素的标记放到堆的终端的后面的位置上. 下面具体的代码实现:
- ElementType
- DeleteMin(PriorityQueue H){
- int i, Chid;
- ElementType MinElement, LastElement;
- if(IsEmpty(H)){
- return H->Element[0];
- }
- MinElement = H->Elements[1];
- LastElement = H->Element[H->Size--];
- for(i = 1; i*2 <H->Size; i = Chid){
- Chid = i * 2;
- if(Chid != H->Size && H->Elements[Chid+1] <H->Elements[Chid])
- Chid++;
- if(LastElement> H->Elements[Chid])
- H->Elements[i] = H->Elements[Chid];
- else
- break;
- }
- H->Elements[i] = LastElement;
- return MinELement;
- }
平均运行时间为 O(logN).
其他的堆操作
虽然求最小值的操作可以在常数时间完成, 但是按照最小元设计的堆对于求最大元方面却是无任何帮助. 事实上, 一个堆蕴含的关于序的信息很少, 若不会整个堆进行线性所受搜索, 是不能找出特定元素的, 虽然我们知道最大元在树叶上面, 但是半数的元素在树叶上面.
构建堆
BuildHeap 操作把 N 个关键字作为输入并把它们放在堆中, 可以通过 Insert 操作进行完成, 由于每个 Insert 操作花费的时间是 O(1), 总的时间是 O(N). 一般的算法是将 N 个关键字以任意的顺序放入树中, 保持结构特性, 然后再开始对父节点进行下虑操作, 遍历所有的父节点之后, 堆将会满足堆序性.
定理
包含 2^(b+1) - 1 个节点, 高为 h 的理想二叉树的节点的高度为 2^(b+1) - 1 - (b+1).
证明: 高度为 b 上面的节点有 1 个, 高度 b-1 上面的节点 2 个, 高度为 b-2 上面的节点 2^2 个..... 一般的高度 b-i 上的节点 2^i 个, 所以所有节点的高度的和是:
S = sum(2^i)(b-i)
通过左乘 2 相减相消就能够求和.
完全树不是理想二叉树, 一个完全二叉树节点树是 2^b 和 2^(b+1)之间.
虽然我们得到的结果对证明 BulidHeap 是线性的而言是充分的, 但是高度的和的界却是尽可能强的.
下面是一个完整例程:
- #include<stdio.h>
- #include<stdlib.h>
- using namespace std;
- typedef int ElementType;
- typedef struct HeadStruct *PriorityQueue;
- #define MinPQSize 10
- #define MinData 0
- struct HeadStruct{
- int Capacity;
- int size;
- ElementType *Elements;
- };
- // 优先队列的初始化
- PriorityQueue Initialze(int MaxElements){
- PriorityQueue H;
- if(MaxElements <MinPQSize){
- printf("Priority QUeue is too small\n");
- }
- H = new HeadStruct();
- H->Elements = new ElementType[MaxElements + 1];
- H->Capacity = MaxElements;
- H->size = 0;
- H->Elements[0] = MinData;
- return H;
- }
- // 优先队列插入元素
- void insert(ElementType x, PriorityQueue H){
- int i;
- if(H == NULL){
- printf("Priority queue is Full \n");
- return;
- }
- for(i=++H->size; H->Elements[i/2]>x; i/=2){
- H->Elements[i] = H->Elements[i/2];
- }
- H->Elements[i] = x;
- }
- // 优先队列删除最小元
- ElementType DeletMin(PriorityQueue H){
- int i, child;
- ElementType MinElement, LastElement;
- if(H == NULL){
- printf("PriorityQueue is null\n");
- return H->Elements[0];
- }
- MinElement = H->Elements[1];
- LastElement = H->Elements[H->size--];
- for(i=1; 2*i<=H->size; i=child){
- child = i*2;
- if(child != H->size && H->Elements[child +1] <H->Elements[child]){
- child++;
- }
- if(LastElement> H->Elements[child]){
- H->Elements[i] = H->Elements[child];
- }else{
- break;
- }
- }
- H->Elements[i] = LastElement;
- return MinElement;
- }
- void printfPriorityQueue(PriorityQueue H){
- for(int i=1; i<=H->size; i++){
- printf("%d", H->Elements[i]);
- }
- }
- int main(){
- PriorityQueue H = Initialze(50);
- int list[10] = {13,21,16,24,31,19,68,65,26,32};
- for(int i=0; i<10; i++){
- insert(list[i], H);
- }
- insert(14, H);
- printfPriorityQueue(H);
- int min = DeletMin(H);
- printf("min: %d\n", min);
- printfPriorityQueue(H);
- }
d - 堆
d 堆是二叉堆的推广, 它恰像一个二叉堆, 只是所有的节点都有 d 个儿子(因此, 二叉堆是 2 堆).d 堆显然要比二叉堆浅的多, 它将 Insert 时间改进为 O(logdN). 然而, 对于大的 d,DeleteMin 操作费时用的多, 因为虽然树浅了, 但是 d 个儿子中的最小者是必须要找出的, 使用标准的算法, 这会花费 d-1 次. 虽然仍然是一个数组, 找出儿子和父亲都有个因子 d, 除非 d 是 2 的幂, 否则将会大大的增加运行时间, 因为我们不能时间二进制的移位计算了. 当优先队列太大不能完全装入主存时, d 堆也是很有用的. 在这种情况下, d 堆能够以于 B 树大致相同的方式发挥作用. 在实践过程中, 4 - 堆可以胜过二叉堆.
除了不能执行 Find 外, 堆的实现的最明显的缺点是: 将两个堆合并成一个堆是困难的, 这种附加的操作叫做 Merge, 存在许多的实现堆的方法使得 Merge 操作的运行时间是 O(logN).
左式堆
设计一种堆结构像二叉树那样高效地支持合并操作 (即以 O(N) 时间处理一次 Merge)而且只使用一个数组似乎很困难. 原因在于, 合并似乎需要把一个数组拷贝到另外一个数组中去, 对于相同大小的堆这将花费时间 O(N), 正是因为如此, 所有支持合并的高级数据结构都需要使用指针.
类似二叉堆那样, 左式堆也具有结构性和有序性. 事实上, 和所有使用的堆一样, 左式堆具有时间的堆序性质. 左式堆也是二叉树, 左式堆和二叉树唯一的区别是: 左式堆不是理想平衡的, 而实际上是趋向于非常不平衡.
左式堆的性质
我们把任一节点的零路径长 Npl 定位为从 X 到一个没有两个儿子的节点的最短路径长. 因此, 具有 0 个或者 1 个儿子的节点 Npl 为 0, 而 Npl(NULL)=-1. 任一节点的零路径长比它的诸儿子节点的零路径长的最小值多 1, 这个结论也适合用少于两个儿子的节点.
左式堆性质是: 对于堆中的每一个节点 X, 左儿子的零路径长至少与右儿子的零路径长一样大. 这个性质实际上超出了平衡的要求, 因为它显然更偏向于使树向左增加深度. 确实有可能存在左节点形成的长路径构成的树, 因此, 我们就有了左式堆. 左式堆趋向于加深左路径, 所以右路径应该短. 否则就会存在一条路径上通过某个节点 X 并取得做儿子, 此时 X 则破坏了左式堆的性质.
在右路径上有 r 个节点的左式树必然至少有 2^r - 1 个节点.
对左式堆的基本操作是合并, 插入只是合并的特殊情形, 因为我们可以把插入看成是单节点堆与一个大的堆的 Merge.
下面是具体的代码实现:
struct TreeNode; typedef struct TreeNode *PriorityQueue; struct TreeNode{ ElementType Element; PriorityQueue Left; PriorityQueue Right; int Npl; }
合并左式堆的驱动例程
PriorityQueue Merge(PriorityQueue H1, PriorityQueue H2){ if(H1 == NULL) return H2; if(H2 == NULL) return H1; if(H1->Element <H2->Element) Merge1(H1, H2); else Merge1(H2, H1); } static PriorityQueue Merge1(PriorityQueue H1, PriorityQueue H2){ if(H1->Left == NULL) H1->Left = H2; else{ H1->Right = Merge(H1->Right, H2); if(H1->Left->Npl <H1->Right->Npl) SwapChildren(H1); H1->Npl = H1->Right->Npl + 1; } return H1; }
左式堆的插入例程
PriorityQueue Insert1(ElementType X, PriorityQueue H){ PriorityQueue SingleNode; SingleNode = malloc(sizeof(struct TreeNode)); if(SingNode == NULL){ FatalError("out of space"); }else{ SingleNode->Element = X; SingleNode->Npl = 0; SingleNode->Left = SingleNode->Right = NULL; H = Merge(SingleNode, H); } return H; } PriorityQueue DeleteMin1(PriorityQueue H){ PriorityQueue LeftHeap, RightHeap; if(IsEmpty(H)){ Error("empty"); return H; } LeftHeap = H->Left; RRightHeap = H->Right; free(H); return Merge(LeftHeap, RightHeap); }
斜堆
斜堆是左式堆的自调节形式, 实现起来及其简单, 斜堆和左式堆的关系类似于伸展树和 AVL 树间的关系. 斜堆是具有堆序的二叉树, 但是不存在堆树的结构的限制. 不同于左式堆, 关于任意节点的零路径长的任何信息都不保存. 斜堆的左路径在任意时刻都可以任意长, 因此所有操作的最坏情形运行时间均为 O(N). 然而, 正如伸展树一样, 任意 M 次操作, 总的最坏运行时间是 O(MlogN). 因此斜堆每次操作的摊还时间是 O(logN).
二项队列
虽然左式堆和斜堆每次操作花费 O(logN)时间, 这有效地支持了合并, 插入和 DeleteMin. 但是还有改进的余地, 因为二叉堆每次操作花费常数平均时间支持插入. 二项队列支持所有这三种操作, 每次操作的最坏情形运行时间是 O(logN), 而插入操作平均花费常数时间.
二项队列不同于我们已经看到的所有优先队列的实现之处是, 一个二项队列不是一颗堆序的树, 而是堆序树的集合, 称为森林. 堆序树中的每一个树都是有约束的形式, 叫二项树. 每个高度上至多存在一颗二项树. 高度为 0 的二项树是一颗单节点树; 高度为 k 的二项树 Bk 通过一颗二项树 Bk-1 附接到另一颗二项树 Bk-1 的根上. 下图显示了二项树 B0,B1,B2,B3.
来源: https://www.cnblogs.com/baby-lily/p/12215692.html