二叉堆：一般我们拿来用的就是最大堆和最小堆。
最小堆：每个节点的值比它的左右子节点的值要大。
代码实现如下：参考Mark Allen Weiss《数据结构和算法分析》（第二版）
1 #include2 #include 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 // 以下滤的方式来建堆（对已有的数组进行排序，使之符合最小堆的堆序heap order）。117 // 参数i为数组对应的二叉堆的内部节点，下滤操作将之放到比左右子节点都小的位置上。 118 void119 PercDown(heap h, int i) 120 {121 int child;122 int tmp;123 124 for (tmp = h->items[i]; 2*i <= h->size; i = child) {125 child = 2*i;126 if (child != h->size && h->items[child] > h->items[child+1]) {127 child++;128 }129 if (tmp > h->items[child]) {130 h->items[i] = h->items[child];131 } else {132 break;133 }134 }135 h->items[i] = tmp;136 }137 138 int 139 main(int argc, char** argv)140 {141 int arr[6] = { 17, 11, 2, 23, 5, 7};142 143 heap h;144 h = InitHeap(6);145 //BuildHeap(h, arr, 6);146 // build heap147 for (int i = 0; i < 6; i++) {148 h->items[++h->size] = arr[i];149 150 }151 for (int i = 6/2; i > 0; i--) {152 PercDown(h, i);153 }154 155 for (int i = 1; i <= h->size; i++) {156 printf("%d\t", h->items[i]);157 }158 printf("\n");159 160 // test DeleteMin, out put a sorted array161 int sortedArr[6] = { 0};162 for (int i = 0; i < 6; i++) {163 sortedArr[i] = DeleteMin(h);164 }165 for (int i = 0; i < 6; i++) {166 printf("%d\t", sortedArr[i]);167 }168 printf("\n");169 170 system("pause");171 172 return 0;173 }