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