最小-最大堆的实现

最小-最大堆的实现：

/*最小最大堆的性质：1. 对于在偶数深度上的任意节点X，存储在X上的关键字小于它的父亲但是大于它的祖父2. 对于在奇数深度上的任意节点X，存储在X上的关键字大于它的父亲但是小于它的祖父从其中可以推理出：1.任意节点X，其关键字的值必定在它的父亲和其祖父之间，也就是说X所在的层上所有关键字  的值必定处于它的父亲层和它的祖父层之间2.所有偶数层从根向下关键字的值递增，所有奇数层从根向下关键字的值递减3.所有奇数层的关键字值大于偶数层的关键字值4.如何判定一个节点X是在奇数层还是偶数层：就是判定X节点的祖父节点在奇数层还是偶数层，  递归的方法就可以实现，{ while(i>1) i/=4; if(i==1) 偶数层 ; if(i==0) 奇数层 ; } 其中  i是节点X的位置。时间复杂度是O(logN)  另外一种方法，根据3.如果X的节点值小于其父亲的节点值，则X在偶数层上，前提是X的值满足最大最小  堆的性质，同时X的值和其父亲的值不相等5.一个最大最小堆的例子                        1             /                    \            19                    15        /        \            /        \       2          4          3          6    /     \    /     \    /     \    /     \   16     18  9      10  7      12  13     14  /  \   /  \ 5   11 8   17*/#include <stdio.h>#include <string.h>#include <stdlib.h>typedef struct MinMaxStruct* MinMaxHeap;typedef int Position;typedef int ElementType;#define MinElement 0#define MaxElement 0x00ffffffstruct MinMaxStruct{int Capacity;int Size;ElementType* Elements;};static intIsEmpty(MinMaxHeap H){return H->Size ? 0 : 1;}static intIsFull(MinMaxHeap H){return H->Size == H->Capacity;}static MinMaxHeapInitalize(int MaxElements){MinMaxHeap H;int Size;Size = sizeof(struct MinMaxStruct) + (MaxElements + 1) * sizeof(ElementType);H = malloc(Size);if(H == NULL) return NULL;H->Capacity = MaxElements;H->Size = 0;H->Elements = (ElementType*)(H + 1);H->Elements[0] = MinElement;return H;}static voidDestroy(MinMaxHeap H){H->Capacity = 0;H->Size = 0;free(H);}/* * 上滤：节点值从大变小的过程叫做上滤 * 上滤的过程包括从根开始向下的所有奇数层，转换到偶数层后 * 再从底部向上经历所有的偶数层 * 插入：在树的底端进行，要么经过上滤到偶数层上，要么 * 下滤到奇数层上 * 删除最大值：从堆的2或3的位置求出最大值，把对最后一个 * 数据放到最大值的位置，然后经过一个完整的上滤过程 * DecreaseKey：减小关键字的值，是将关键字位置减少后，对 * 其经历一个完整的上滤过程 */static PositionPercolateUp(Position i, MinMaxHeap H){Position j = i;ElementType X;H->Elements[0] = MinElement;X = H->Elements[i];while(j>1) j = j >> 2;/* 奇数层,先下滤,再上滤,偶数层直接上滤 */if(j==0){/* 下滤到一个奇数层上 */for( ; i*4 < H->Size; i = j){int k;j = k = 4*i;if(H->Size>=k+1 && H->Elements[j] < H->Elements[k+1]) j = k+1;if(H->Size>=k+2 && H->Elements[j] < H->Elements[k+2]) j = k+2;if(H->Size>=k+3 && H->Elements[j] < H->Elements[k+3]) j = k+3;if(H->Elements[j] > X)H->Elements[i] = H->Elements[j];elsebreak;}H->Elements[i] = X;/* 进行奇偶层互换,把偶数层上的一个最大值替换到奇数层上 */j = i*2;if(j < H->Size)  //j的值最大可以是H->Size-1为偶数,H->Size是奇数值{if(H->Elements[j] < H->Elements[j+1]) j++;}else if(j > H->Size) j = i/2;if(H->Elements[j] > X){H->Elements[i] = H->Elements[j];i = j;}elsereturn i;}/* 上滤 */for( ; H->Elements[i/4] > X ; i /= 4)H->Elements[i] = H->Elements[i/4];H->Elements[i] = X;return i;}/* * 下滤：节点值从小变大的过程叫做下滤 * 下滤的过程包括从根开始向下的所有偶数层，转换到奇数层后 * 再从底部向上经历所有的奇数层 * 插入：在树的底端进行，要么经过上滤到偶数层上，要么 * 下滤到奇数层上 * 删除最小值：从堆的1位置求出最小值，把对最后一个 * 数据放到1位置上，然后经过一个完整的下滤过程 * IncreaseKey：增大关键字的值，是将关键字位置增加后，对 * 其经历一个完整的下滤过程 */static PositionPercolateDown(Position i, MinMaxHeap H){int j = i;ElementType X;H->Elements[0] = MaxElement;X = H->Elements[i];while(j>1) j = j >> 2;/* 偶数层,先下滤,再上滤,奇数层直接上滤 */if(j==1){/* 下滤到一个偶数层上 */for( ; i*4 < H->Size; i = j){int k;j = k = 4*i;if(H->Size>=k+1 && H->Elements[j] > H->Elements[k+1]) j = k+1;if(H->Size>=k+2 && H->Elements[j] > H->Elements[k+2]) j = k+2;if(H->Size>=k+3 && H->Elements[j] > H->Elements[k+3]) j = k+3;if(H->Elements[j] < X)H->Elements[i] = H->Elements[j];elsebreak;}H->Elements[i] = X;/* 进行奇偶层互换,把奇数层上的一个最小值替换到偶数层上 */j = i*2;if(j < H->Size)  //j的值最大可以是H->Size-1为偶数,H->Size是奇数值{if(H->Elements[j] > H->Elements[j+1]) j++;}else if(j > H->Size) j = i/2;if(H->Elements[j] < X){H->Elements[i] = H->Elements[j];i = j;}elsereturn i;}/* 上滤 */for( ; H->Elements[i/4] < X ; i /= 4)H->Elements[i] = H->Elements[i/4];H->Elements[i] = X;return i;}/* * 插入： * 在堆的最后的位置插入关键字，要么经历上滤过程 * 要么经历下滤过程 */static voidInsert(ElementType X, MinMaxHeap H){Position i;if(IsFull(H)) return ;i = ++H->Size;H->Elements[i] = X;i=PercolateUp(i, H);if(i==H->Size)PercolateDown(i, H);}/* * 删除最小值： * 将1号位置的值取下来，把最后一个元素放到此处 * 然后经历一个完整的下滤过程 */static ElementTypeDeleteMin(MinMaxHeap H){ElementType Min;if(IsEmpty(H)) return MinElement;Min = H->Elements[1];H->Elements[1] = H->Elements[H->Size--];PercolateDown(1, H);return Min;}/* * 查找最小值 */static ElementTypeFindMin(MinMaxHeap H){return H->Elements[1];}/* * 删除最大值： * 对2和3号位置比较大小后，把最后一个元素放到此处 * 然后经历一个完整的上滤过程 */static ElementTypeDeleteMax(MinMaxHeap H){int i;ElementType Max;if(IsEmpty(H)) return MaxElement;if(H->Elements[2] < H->Elements[3]){Max = H->Elements[3];i = 3;}else{Max = H->Elements[2];i = 2;}H->Elements[i] = H->Elements[H->Size--];PercolateUp(i, H);return Max;}/* * 查找最大值 */static ElementTypeFindMax(MinMaxHeap H){return H->Elements[2] < H->Elements[3] ?H->Elements[3] : H->Elements[2];}/* * 减小关键字的值 * 对i位置的值减小后执行上滤过程 */static voidDecreaseKey(Position i, ElementType Delta, MinMaxHeap H){if(i <= H->Size){H->Elements[i] -= Delta;PercolateUp(i, H);}}/* * 增加关键字的值 * 对i位置的值增加后执行下滤过程 */static voidIncreaseKey(Position i, ElementType Delta, MinMaxHeap H){if(i <= H->Size){H->Elements[i] += Delta;PercolateDown(i, H);}}/* * 删除关键字 * 把最后一个位置的值放到i位置 * 如果删除值比最后一个值小，相当于增加了i位置的值， * 执行下滤过程 * 如果删除值比最后一个值大，相当于减小了i位置的值， * 执行上滤过程 */static voidDelete(Position i, MinMaxHeap H){ElementType Del;if(i <= H->Size){Del = H->Elements[i];H->Elements[i] = H->Elements[H->Size--];if(Del < H->Elements[i])PercolateDown(i, H);else if(Del > H->Elements[i])PercolateUp(i, H);}}/* * 测试例程  */void MinMaxHeapTest(void){int i;MinMaxHeap H;H = Initalize(1000);if(H==NULL) return;for(i=1; i<1000; i++)Insert(i,H);IncreaseKey(1,1000,H);for(i=0; i<400; i++){printf("% 3d--% 3d\n",DeleteMin(H), DeleteMax(H));}Destroy(H);}