D&F学数据结构系列—

二叉堆（binary heap）

二叉堆数据结构是一种数组对象，它可以被视为一棵完全二叉树。同二叉查找树一样，堆也有两个性质，即结构性和堆序性。对于数组中任意位置i上的元素，其左儿子在位置2i上，右儿子在左儿子后的单元2i+1中，它的父亲在[i/2]（向下取整）中。在一个小顶堆中，对于每一个节点X,X的父亲中的关键字小于（或等于）X中的关键字，根节点除外（它没有父亲）。

因此，一个数据结构将由一个数组、一个代表最大值的整数、以及当前的堆的大小组成。一个典型的优先队列（priority queue）如下：

 #ifndef _BinHeap_H

 struct HeapStruct;

 typedef struct HeapStruct *PriorityQueue;

 PriorityQueue Initialize(int MaxElements);

 void Destroy(PriorityQueue H);

 void MakeEmpty(PriorityQueue H);

 void Insert(ElementType X,PriorityQueue H);

 ElementType DeleteMin(PriorityQueue H):

 ElementType FinMin(PriorityQueue H);

 int IsEmpty(PriorityQueue H);

 int IsFull(PriorityQueue H);

 #endif

 struct HeapSrtuct

 {

    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));

    if(H==NULL)

      FatalError("Out of space!");

    /*分配数组时多分配一个单位给哨兵*/

    H->Elements=malloc((MaxElements+)*sizeof(ElementType));

    if(H->Elements==NULL)

      FatalError("Out of space!");

    H->Capacity=MaxElements;

    H->Size=;

    H->Element[]=MinData;

    return H;

 }

基本的堆操作：

Insert（插入）

为将一个元素X插入到堆中，我们在下一个空闲位置创建一个空穴，否则该堆将不是完全二叉树。如果X可以放在该空穴中而并不破坏堆的序，那么插入完成。否则，我们把空穴的父节点上的元素移入该空穴中，这样，空穴就朝着根的方向上行一步。继续该过程直到X能被放入空穴中为止。这种策略叫做上滤（percolate up）；

 /* H->Element[0] is a sentinel */

 void Insert(ElementType X,PriorityQueue H)

 {

    int i;

    if(IsFull(H))

    {

      Error("priority queue is full");

      return;

     }

      for(i=++H->Size;H->Elements[i/]>X;i/=)

        H->Elements[i]=H->Elements[i/];

      H->Elements[i]=X;

 }

程序并没有通过“反复交换直至建立正确的序”这种方法实现上滤过程，因为一次交换需要三条赋值语句，如果一个元素上滤d层，那么由于交换而产生的赋值语句就到达3d，这里的方法只用d+1次赋值。

如果要插入的元素是新的最小值，那么它将一直被推向顶端。这样在某一时刻，i将是1，我们就需要令程序跳出while循环。当然我们可以使用明确的测试做到这一点，不过，我们采用的是把一个很小的值放到位置0处以使while循环得以终止。这个值必须小于堆中的任何值，我们称之为标记（sentinel）。这种想法类似于链表头结点的使用。通过添加一条哑信息（dummy piece of information），我们避免了每个循环都要执行一次的测试，从而节省了一些时间。

DeleteMin（删除最小元）

当删除一个最小元时，在根节点出产生了一个空穴。由于现在堆少了一个元素，因此堆中随后一个元素X必须移动到该堆的某个地方。我们将空穴的两个儿子中较小者移入空穴，这样就把空穴向下推了一层。重复该步骤直到X可以被放入空穴中。这种策略叫做下滤（percolate down）。

在上图中，删除13后，我们必须要正确地将31放到堆中。

 ElementType DeleteMin(PriorityQueue H)

 {

    int i,Child;

    ElementType MinElement,LastElement;

    if(IsEmpty(H))

    {

      Error("Priority queue is empty");

      return H->Elements[];

    }

    MinElement=H->Elements[];

    LastElement=H->Elements[H->Size--];

    for(i=;i*<=H->Size;i=Child)

    {

      /*找到最小的孩子*/

      Child=i*;

      if(Child!=H->Size&&H->Elements[Child+]<H->Elements[Child])

      Child++;

      /*下沉一层*/

      if(LastElement>H->Elements[Child])

        H->Elements[i]=H->Elements[Child];

      else

        break;

    }

    H->Elements[i]=LastElement;

    return MinElement;

 }

其它的堆操作：

DecreaseKey（降低关键字的值）

DecreaseKey(P,Δ,H)操作降低在位置P处的关键字的值，降值的幅度为正的量Δ。通过上滤调整堆。该操作对系统管理程序是有用的：系统管理程序能够使它们的程序以最高优先级来运行。

IncreaseKey（增加关键字的值）

IncreaseKey(P,Δ,H)操作增加在位置P处的关键字的值，增值的幅度为正的量Δ。通过下滤调整堆。许多调度程序自动地降低正在过多消耗CPU的进程的优先级。

Delete（删除）

Delete(P,H)操作删除堆中位置P上的节点。者通过首先执行DecreaseKey(P,∞，H)，然后再执行DeleteMin(H)来完成。当一个进程被用户终止（而不是正常终止）时，它必须从优先队列中除去。

BuildHeap（构建堆）

BuildHeap(H)操作把N个关键字作为输入并把它们放入堆中。可以使用N个相继的Insert（插入操作来实现。平均时间是O(N)。

巴特西

D&F学数据结构系列——二叉堆

最新文章

热门文章