二叉堆.zip

/* 这里实现的是最小堆 */ #include "binheap.h" #include "fatal.h" #include <stdlib.h> #define MinPQSize (10) // 堆最小的尺寸 #define MinData (-32767) // 堆的结构 struct HeapStruct { int Capacity; // 代表最大值 int Size; // 当前的堆大小 ElementType *Elements; // 数组 }; /* START: fig6_0.txt */ /** * 初始化堆 * @param MaxElements 最大的容量 * @return 指向最大堆的指针 */ PriorityQueue Initialize( int MaxElements ) { PriorityQueue H; /* 1*/ if( MaxElements < MinPQSize ) /* 2*/ Error( "Priority queue size is too small" ); /* 3*/ H = malloc( sizeof( struct HeapStruct ) ); /* 4*/ if( H ==NULL ) /* 5*/ FatalError( "Out of space!!!" ); /* Allocate the array plus one extra for sentinel */ /* 6*/ H->Elements = malloc( ( MaxElements + 1 ) * sizeof( ElementType ) ); // 给数组分配空间 /* 7*/ if( H->Elements == NULL ) /* 8*/ FatalError( "Out of space!!!" ); /* 9*/ H->Capacity = MaxElements; // H 的容量 /*10*/ H->Size = 0; // 当前的堆大小 /*11*/ H->Elements[ 0 ] = MinData; /*12*/ return H; } /* END */ void MakeEmpty( PriorityQueue H ) { H->Size = 0; } /* START: fig6_8.txt */ /* H->Element[ 0 ] is a sentinel */ /** * 插入操作 * @param X 待插入的元素 * @param H 要插入的目标堆 */ void Insert( ElementType X, PriorityQueue H ) { int i; if( IsFull( H ) ) { Error( "Priority queue is full" ); return; } // 上滤(percolate up)，如果父节点比 X 大，就将其给滤下来 for( i = ++H->Size; H->Elements[ i / 2 ] > X; i /= 2 ) H->Elements[ i ] = H->Elements[ i / 2 ]; H->Elements[ i ] = X; // 最后剩下的位置就是 X 应该插入的位置 } /* END */ /* START: fig6_12.txt */ /** * 删除最小元 * @param H * @return 返回最小元 */ ElementType DeleteMin( PriorityQueue H ) { int i, Child; ElementType MinElement, LastElement; /* 1*/ if( IsEmpty( H ) ) { /* 2*/ Error( "Priority queue is empty" ); /* 3*/ return H->Elements[ 0 ]; } /* 4*/ MinElement = H->Elements[ 1 ]; // 根节点即最小元 /* 5*/ LastElement = H->Elements[ H->Size-- ]; // 取出最后一个元素，用于插入到删除最小元之后的根节点处，然后下滤 /* 6*/ for( i = 1; i * 2 <= H->Size; i = Child ) { /* Find smaller child */ /* 7*/ Child = i * 2; /* 8*/ if( Child != H->Size && H->Elements[ Child + 1 ] /* 9*/ < H->Elements[ Child ] ) /*10*/ Child++; /* Percolate one level 下滤操作 */ /*11*/ if( LastElement > H->Elements[ Child ] ) /*12*/ H->Elements[ i ] = H->Elements[ Child ]; else /*13*/ break; } /*14*/ H->Elements[ i ] = LastElement; /*15*/ return MinElement; } /* END */ /** * 查找最小元，即取出根节点存储的元素 * @param H * @return */ ElementType FindMin( PriorityQueue H ) { if( !IsEmpty( H ) ) return H->Elements[ 1 ]; Error( "Priority Queue is Empty" ); return H->Elements[ 0 ]; } /** * 判断堆是否为空 * @param H * @return */ int IsEmpty( PriorityQueue H ) { return H->Size == 0; } /** * 判断堆是否已满 * @param H * @return */ int IsFull( PriorityQueue H ) { return H->Size == H->Capacity; } /** * 销毁堆 * @param H */ void Destroy( PriorityQueue H ) { free( H->Elements ); free( H ); } #if 0 /* START: fig6_14.txt */ for( i = N / 2; i > 0; i-- ) PercolateDown( i ); /* END */ #endif