[cpp] 最小-最大堆的實現： [cpp] /* 最小最大堆的性質： 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 0x00ffffff struct MinMaxStruct { int Capacity; int Size; ElementType* Elements; }; static int IsEmpty(MinMaxHeap H) { return H->Size ? 0 : 1; } static int IsFull(MinMaxHeap H) { return H->Size == H->Capacity; } static MinMaxHeap Initalize(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 void Destroy(MinMaxHeap H) { H->Capacity = 0; H->Size = 0; free(H); } /* * 上濾：節點值從大變小的過程叫做上濾 * 上濾的過程包括從根開始向下的所有奇數層，轉換到偶數層後 * 再從底部向上經歷所有的偶數層 * 插入：在樹的底端進行，要麼經過上濾到偶數層上，要麼 * 下濾到奇數層上 * 刪除最大值：從堆的2或3的位置求出最大值，把對最後一個 * 數據放到最大值的位置，然後經過一個完整的上濾過程 * DecreaseKey：減小關鍵字的值，是將關鍵字位置減少後，對 * 其經歷一個完整的上濾過程 */ static Position PercolateUp(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]; else break; } 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; } else return 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 Position PercolateDown(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]; else break; } 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; } else return i; } /* 上濾 */ for( ; H->Elements[i/4] < X ; i /= 4) H->Elements[i] = H->Elements[i/4]; H->Elements[i] = X; return i; } /* * 插入： * 在堆的最後的位置插入關鍵字，要麼經歷上濾過程 * 要麼經歷下濾過程 */ static void Insert(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 ElementType DeleteMin(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 ElementType FindMin(MinMaxHeap H) { return H->Elements[1]; } /* * 刪除最大值： * 對2和3號位置比較大小後，把最後一個元素放到此處 * 然後經歷一個完整的上濾過程 */ static ElementType DeleteMax(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 ElementType FindMax(MinMaxHeap H) { return H->Elements[2] < H->Elements[3] ? H->Elements[3] : H->Elements[2]; } /* * 減小關鍵字的值 * 對i位置的值減小後執行上濾過程 */ static void DecreaseKey(Position i, ElementType Delta, MinMaxHeap H) { if(i <= H->Size) { H->Elements[i] -= Delta; PercolateUp(i, H); } } /* * 增加關鍵字的值 * 對i位置的值增加後執行下濾過程 */ static void IncreaseKey(Position i, ElementType Delta, MinMaxHeap H) { if(i <= H->Size) { H->Elements[i] += Delta; PercolateDown(i, H); } } /* * 刪除關鍵字 * 把最後一個位置的值放到i位置 * 如果刪除值比最後一個值小，相當於增加了i位置的值， * 執行下濾過程 * 如果刪除值比最後一個值大，相當於減小了i位置的值， * 執行上濾過程 */ static void Delete(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); }
