1 #include <cstdio>  2 #include <cstdlib>  3   4 #define MIN (1<<(sizeof(int)*8-1))  5   6 typedef int Item;  7 typedef struct HeapStruct* heap;  8   9 struct HeapStruct { 10     int capacity;  // capacity的大小为堆的元素加1。  11     int size;      // size指向堆中最后一个元素，size=0时堆为空  12     Item* items;   // items的第一个元素存放sentinel，其余元素存放堆中内容。  13 }; 14 // 初始化堆的三个参数  15 heap 16 InitHeap(int maxItems) 17 { 18     heap h; 19      20     h = (heap)malloc(sizeof(struct HeapStruct)); 21     if (h == NULL) { 22         printf("out of space.\n"); 23         return NULL; 24     } 25      26     h->items =(Item*)malloc((maxItems+1)*sizeof(Item)); // 用h->items[0]来存放sentinel  27     if (h->items == NULL) { 28         printf("out of space.\n"); 29         return NULL; 30     } 31      32     h->capacity = maxItems; 33     h->size = 0; 34     h->items[0] = MIN; 35      36     return h; 37 } 38    39 int 40 IsFull(heap h) 41 { 42     if (h->size == h->capacity) { 43         return 1; 44     } else { 45         return 0; 46     } 47 } 48  49 int 50 IsEmpty(heap h) 51 { 52     if (h->size == 0) { 53         return 1; 54     } else { 55         return 0; 56     } 57 } 58    59 Item 60 FindMin(heap h) 61 { 62     return h->items[1]; 63 } 64 // 向最小堆插入元素。   65 void 66 Insert(Item item, heap h) 67 { 68     if (IsFull(h)) { 69         printf("Insert failed. Because the heap is full.\n"); 70         return; 71     } 72     // percolate up，将item往上，一步一步放到合适的地方。 73     int i;  74     for (i = ++h->size; h->items[i/2] > item; i /= 2) { 75         h->items[i] = h->items[i/2]; 76     } 77     h->items[i] = item; 78 } 79 // 在最小堆中删除元素。 返回最小值。  80 Item 81 DeleteMin(heap h) 82 { 83     if (IsEmpty(h)) { 84         printf("Delete failed. Because the heap is empty.\n"); 85         return h->items[0]; 86     } 87      88     Item minItem = h->items[1]; 89     Item lastItem = h->items[h->size--]; // 此函数目的就是把lastItem放到合适位置  90     // percolate down，将lastItem往下，一步一步往下寻找合适的地方。 91     int i, child; 92     for (i = 1; 2*i <= h->size; i = child) { 93         child = 2 * i; 94         // 将child放在左右子树中较小的那个位置上 95         if (child != h->size && h->items[child] > h->items[child+1]) { 96             child++; 97         } 98          99         if (lastItem > h->items[child]) {100             h->items[i] = h->items[child];101         } else {102             break;103         }104     }105     h->items[i] = lastItem;106     return minItem;107 }108 // 以插入的方式来建堆。复杂度为O(NlogN)，因为有N个元素，每次插入花费logN时间。      109 void110 BuildHeap(heap h, Item arr[], int len)111 {112     for (int i = 0; i < len; i++) {113         Insert(arr[i], h);114     }115 }116           117 118 int 119 main(int argc, char** argv)120 {121     int arr[6] = {17, 11, 2, 23, 5, 7};122     123     heap h;124     h = InitHeap(6);125     BuildHeap(h, arr, 6);126     127     for (int i = 1; i <= h->size; i++) {128         printf("%d\t", h->items[i]);129     }130     printf("\n");131     132     // test DeleteMin, out put a sorted array133     int sortedArr[6] = {0};134     for (int i = 0; i < 6; i++) {135         sortedArr[i] = DeleteMin(h);136     }137     for (int i = 0; i < 6; i++) {138         printf("%d\t", sortedArr[i]);139     }140     printf("\n");141     142     system("pause");143     144     return 0;145 }