首页 > 代码库 > D&F学数据结构系列——二叉堆

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

2024-07-15 12:44:28   214人阅读

二叉堆（binary heap）

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

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

 1 #ifndef _BinHeap_H 2 struct HeapStruct; 3 typedef struct HeapStruct *PriorityQueue; 4 PriorityQueue Initialize(int MaxElements); 5 void Destroy(PriorityQueue H); 6 void MakeEmpty(PriorityQueue H); 7 void Insert(ElementType X,PriorityQueue H); 8 ElementType DeleteMin(PriorityQueue H): 9 ElementType FinMin(PriorityQueue H);10 int IsEmpty(PriorityQueue H);11 int IsFull(PriorityQueue H);12 #endif13 14 struct HeapSrtuct15 {16    int Capacity;17    int Size;18    ElementType *Elements;19 };

创建一个空堆：

 1 PriorityQueue Initialize(int MaxElements) 2 { 3    PriorityQueue H; 4    if(MaxElements<MinPQSize) 5      Error("Priority queue size is too small"); 6    H=malloc(sizeof(struct HeapStruct)); 7    if(H==NULL) 8      FatalError("Out of space!"); 9    /*分配数组时多分配一个单位给哨兵*/10    H->Elements=malloc((MaxElements+1)*sizeof(ElementType));11    if(H->Elements==NULL)12      FatalError("Out of space!");13    H->Capacity=MaxElements;14    H->Size=0;15    H->Element[0]=MinData;16    return H;17 }

基本的堆操作：

Insert（插入）

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

 1 /* H->Element[0] is a sentinel */ 2 void Insert(ElementType X,PriorityQueue H) 3 { 4    int i; 5    if(IsFull(H)) 6    { 7      Error("priority queue is full"); 8      return; 9     }10      for(i=++H->Size;H->Elements[i/2]>X;i/=2)11        H->Elements[i]=H->Elements[i/2];12      H->Elements[i]=X;13 }

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

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

 


联系
我们