首页 > 代码库 > 优先队列之二叉堆与d-堆
优先队列之二叉堆与d-堆
二叉堆简介
平时所说的堆，若没加任何修饰，一般就是指二叉堆。同二叉树一样，堆也有两个性质，即结构性和堆序性。正如AVL树一样，对堆的以此操作可能破坏者两个性质中的一个，因此，堆的操作必须要到堆的所有性质都被满足时才能终止。
结构性质
堆是一棵完全填满的二叉树，因为完全二叉树很有规律，所以它可以用一个数组表示而不需要指针。如下图所示，图2中的数组对应图1中的堆。
图1：二叉堆 图2：二叉堆的数组存储
对于任意位置i上的元素，其左儿子在位置2i处，右儿子在位置2i+1处，而它的父亲在i/2。因此，不仅指针这里不需要，而且遍历该树所需要的操作也十分简单。这种表示法的唯一问题在于：最大的堆大小需要事先估计，但对于典型的情况者并不成问题，图2中堆的大小是13个元素。该数组有一个位置0，用做哨兵，后面会有阐述。
因此，一个堆的数据结构将由一个数组，一个代表最大值的整数以及当前堆的大小组成。
堆序性质
使操作能快速执行的性质是堆序性。在一个堆中，对于每个节点X，X的父亲中的关键字小于(或等于)X中的关键字，根节点除外(根节点没有父亲)。图3中，左边的是堆，右边的不是(虚线表示堆序性质被破坏)。
图3：两棵完全二叉树
基本操作
Insert(插入)：
为了将一个元素X插入到堆中，我们在下一个空闲位置创建一个空穴，否则该堆将不是完全树。如果X可以放入到该空穴中，那么插入完成。否则，我们把空穴的父节点上的元素移入该空穴中，这样，空穴就朝着根的方向上行一步。继续该过程直到X能被放入到空穴中为止。图4表示，为了插入14，我们在堆的下一个可用位置建立一个空穴，由于将14插入空穴破坏了堆序性质，因此将31移入该空穴，图5继续这种策略，直到找到14的正确位置。
图4：创建一个空穴，再将空穴上冒 图5：将14插入到前面的堆中的其余两步
这种策略叫做上虑。新元素在堆中上虑直到找出正确的位置；使用如下代码，很容易实现。
如果要插入的元素师新的最小值，那么它将一直被推向顶端，这样在某一时刻，i将是1，我们就需要令程序跳出while循环。当然可以通过明确的测试做到这一点。不过，这里采用的是把一个很小的值放到位置0处以使while循环终止，这个值必须小于堆中的任何值，称之为标记或哨兵。这类似于链表中头结点的使用。通过添加的这个标记，避免了每次循环都要执行一次测试，这是简单的空间换时间策略。
DeleteMin(删除最小元)：
找出最小元是很容易的；困难的部分是删除它。当删除一个最小元时，在根节点处产生了一个空穴。由于现在堆少了一个元素，因此对中最后一个元素X必须移到该堆的某个地方。如果X可以被放入空穴中，那么DeleteMin完成。不过这一般都不可能，因此我们将空穴的两个儿子中较小者移入空穴中，这样就把空穴向下推了一层，重复该步骤，知道X可以被放入空穴中。因此，我们的做法是将X置入沿着从根开始包含最小儿子的一条路径上的一个正确的位置。
图6显示DeleteMin之前的堆，删除13之后，我们必须要正确的将31放到堆中，31不能放在空穴中，因为这将破坏堆序性质，于是，我们把较小的儿子14置入空穴，同时空穴向下滑一层，重复该过程，把19置入空穴，在更下一层上建立一个新的空穴，然后26置入空穴，在底层又建立一个新的空穴，最后，我们得以将31置入空穴中。这种策略叫做下虑。
图6 在根处建立空穴 图7：将空穴下滑一层
typedef int ElementType;#ifndef _BinHeap_H#define MinPQSize 10#define MinData -32767struct HeapStruct;typedef struct HeapStruct *PriorityQueue;PriorityQueue Initialize(int MaxElements);void Destroy(PriorityQueue H);void MakeEmpty(PriorityQueue H);void Insert(ElementType X,PriorityQueue H);ElementType DleteMin(PriorityQueue H);ElementType FindMin(PriorityQueue H);int IsEmpty(PriorityQueue H);int IsFull(PriorityQueue H);#endif
BinHeap.c
#include"BinHeap.h"#include"fatal.h"struct HeapStruct{ int Capacity; int Size; ElementType *Elements;};PriorityQueue Initialize(int MaxElements){ PriorityQueue H; if(MaxElements<MinPQSize) Error("Priority queue size is too small"); H=malloc(sizeof(struct HeapStruct)); 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;}void MakeEmpty(PriorityQueue H){ H->Size=0;}void Insert(ElementType X,PriorityQueue H){ int i; if(IsFull(H)) { Error("Priority queue is full"); } for(i=++H->Size;X<H->Elements[i/2];i=i/2) { H->Elements[i]=H->Elements[i/2]; } H->Elements[i]=X;}ElementType DeleteMin(PriorityQueue H){ int i,Child; ElementType MinElement,LastElement; if(IsEmpty(H)) { Error("Priority queue is empty"); return H->Elements[0]; } MinElement=H->Elements[1]; LastElement=H->Elements[H->Size--]; for(i=1;i<H->Size;i=Child) { Child=2*i; if(Child!=H->Size&&H->Elements[Child]>H->Elements[Child+1]) Child++; if(LastElement>H->Elements[Child]) H->Elements[i]=H->Elements[Child]; else break; } H->Elements[i]=LastElement; return MinElement;}ElementType FindMin(PriorityQueue H){ return H->Elements[1];}int IsEmpty(PriorityQueue H){ return H->Size==0;}int IsFull(PriorityQueue H){ return H->Capacity==H->Size;}void Destroy(PriorityQueue H){ free(H->Elements); free(H);}
UseBinHeap.c
#include <stdio.h>#include <stdlib.h>#include"BinHeap.h"int main(){ int i; PriorityQueue H=Initialize(MinPQSize); MakeEmpty(H); for(i=0;i<MinPQSize;i++) { Insert(i,H); } printf("Hello world!\n"); return 0;}
d-堆
二叉堆因为实现简单，因此在需要优先队列的时候几乎总是使用二叉堆。d-堆是二叉堆的简单推广，它恰像一个二叉堆，只是所有的节点都有d个儿子（因此，二叉堆又叫2-堆）。下图表示的是一个3-堆。注意，d-堆要比二叉堆浅得多，它将Insert操作的运行时间改进为
。然而，对于大的d，DeleteMin操作费时得多，因为虽然树浅了，但是d个儿子中的最小者是必须找到的，如果使用标准算法，将使用d-1次比较，于是将此操作的时间提高到
。如果d是常数，那么当然两种操作的运行时间都为 O(logN)。虽然仍可以使用一个数组，但是，现在找出儿子和父亲的乘法和除法都有个因子d，除非d是2的幂，否则会大大增加运行时间，因为我们不能再通过二进制移位来实现除法和乘法了。D-堆在理论上很有趣，因为存在许多算法，其插入次数比删除次数多得多，而且，当优先队列太大不能完全装入内存的时候，d-堆也是很有用的，在这种情况下，d-堆能够以与B-树大致相同的方式发挥作用。
除了不能执行Find操作外（指以对数执行），堆的实现最明显的两个缺点是：将两个堆合并成一个堆是很困难的。这种附加的操作叫做Merge。存在许多实现堆的方法使得Merge操作的运行时间为O(logN)，如下篇介绍的左式堆。
