现在po一下C语言版本的，留作以后接口使用. 1 #include2 #include 3 4 #define HEAP_SIZE 100 5 #define HEAP_FULL_VALUE -100 6 7 #if 0 8 /*小顶堆存储结构*/ 9 typedef struct small_heap 10 { 11 int data[HEAP_SIZE]; 12 int num; 13 }SMALL_HEAP; 14 #endif 15 16 17 /* 18 * name: heap_Swap 19 * 20 * purpose: 21 * swap two value of heap 22 */ 23 static void heap_Swap(int heap[],int index_src,int index_dst) 24 { 25 int tmp = heap[index_src]; 26 27 heap[index_src] = heap[index_dst]; 28 heap[index_dst] = tmp; 29 } 30 31 /* 32 * name: heap_Up 33 * 34 * purpose: 35 * move up value of the index position to adjust heap struct 36 */ 37 static void heap_Up(int heap[],int index) 38 { 39 int parent = index / 2; 40 41 while(parent >= 1) 42 { 43 if(heap[index] < heap[parent]) 44 { 45 heap_Swap(heap,index,parent); 46 index = parent; 47 } 48 else 49 { 50 break; 51 } 52 } 53 } 54 55 /* 56 * name: heap_Down 57 * 58 * purpose: 59 * move down value of the index position to adjust heap struct 60 */ 61 static void heap_Down(int heap[],int index,int heap_data_num) 62 { 63 if(index * 2 > heap_data_num) 64 { //leaf node can not move down 65 return; 66 } 67 68 while(index * 2 <= heap_data_num ) 69 { 70 int child = index * 2; // left child 71 72 if(child > heap_data_num) 73 { 74 return; 75 } 76 77 if(index * 2 < heap_data_num) 78 { //the node have two child 79 if(heap[child + 1] < heap[child]) 80 { 81 child += 1; //right child is smaller update 82 } 83 84 } 85 86 if(heap[child] < heap[index]) 87 { //the child samller than index swap value 88 heap_Swap(heap,index,child); 89 index = child; 90 } 91 else 92 { 93 break; 94 } 95 } 96 } 97 98 /* 99 * name: heap_Insert100 *101 * purpose:102 * insert a value into heap and ajust heap struct103 */104 void heap_Insert(int heap[],int *heap_data_num,int value)105 {106 if(*heap_data_num == 0)107 {108 heap[0] = HEAP_FULL_VALUE; //data 0 do not save in the heap 109 }110 111 (*heap_data_num)++; //update heap size112 heap[*heap_data_num] = value; //add value to heap113 114 heap_Up(heap,*heap_data_num); //adjust heap struct115 }116 117 /*118 * name: heap_Delete119 *120 * purpose:121 * delete a value from heap122 */123 void heap_Delete(int heap[],int *heap_data_num,int value)124 {125 int index;126 127 for(index = 1; index <= *heap_data_num; index++)128 {129 if(heap[index] == value)130 {131 break;132 }133 }134 135 if(index > *heap_data_num)136 { //the value is not exist137 return;138 }139 140 heap[index] = heap[*heap_data_num]; //set the index value as final value141 142 (*heap_data_num)--;//the final value is not as the heap143 144 heap_Down(heap,index,*heap_data_num); //move down 145 146 int parent = index / 2; 147 if(parent > 0 && heap[index] < heap[parent])148 { //ajust to the special situation149 heap_Up(heap,index);150 } 151 152 heap[*heap_data_num + 1] = HEAP_FULL_VALUE; //delete final data153 }154 155 /*156 * name:heap_Init_Adjust157 *158 * purpose:159 * to adjust the init heap160 * time complex is O(n) better than insert value one by one161 *162 * explain:163 * because the heap is a complete binary tree so just first half of heap data is not leaf node164 *165 */166 void heap_Init_Adjust(int heap[],int heap_data_num)167 {168 int index;169 170 for(index = heap_data_num / 2; index >= 1; index--)171 {172 heap_Down(heap,index,heap_data_num); //adjust the heap struct at index position173 }174 }175 176 void heap_Print(int heap[],int heap_data_num);177 /*178 * name: heap_Sort179 *180 * purpose:181 * to sort the heap to a descending order182 */ 183 void heap_Sort(int heap[],int heap_data_num)184 {185 int index;186 187 for(index = heap_data_num; index > 1; index--)188 {189 heap_Swap(heap,1,index); //swap the heap top with the final value190 heap_Down(heap,1,index - 1); //to ajust the heap struct afert sort one value191 //heap_Print(heap,heap_data_num);192 }193 }194 195 196 /*197 * name: heap_Print198 *199 * purpose:200 * print heap data as commen order201 */202 void heap_Print(int heap[],int heap_data_num)203 {204 int i;205 for(i = 1; i <= heap_data_num; i++)206 {207 printf("%d ",heap[i]);208 }209 210 printf("\n");211 }212 213 214 int main()215 {216 int heap[HEAP_SIZE]; 217 int i,heap_data_num = 0;218 219 for(i = 0; i < heap_data_num; i++)220 {221 heap[i] = HEAP_FULL_VALUE;222 }223 224 #if 1225 heap_Insert(heap,&heap_data_num,1);226 heap_Insert(heap,&heap_data_num,3);227 heap_Insert(heap,&heap_data_num,4);228 heap_Insert(heap,&heap_data_num,5);229 heap_Insert(heap,&heap_data_num,8);230 heap_Insert(heap,&heap_data_num,2);231 heap_Insert(heap,&heap_data_num,7);232 heap_Insert(heap,&heap_data_num,6);233 234 heap_Print(heap,heap_data_num);235 236 heap_Sort(heap,heap_data_num);237 heap_Print(heap,heap_data_num);238 239 heap_Init_Adjust(heap,heap_data_num);240 heap_Print(heap,heap_data_num);241 242 heap_Sort(heap,heap_data_num);243 heap_Print(heap,heap_data_num);244 245 heap_Delete(heap,&heap_data_num,2);246 heap_Print(heap,heap_data_num);247 heap_Delete(heap,&heap_data_num,1);248 heap_Print(heap,heap_data_num);249 250 heap_Sort(heap,heap_data_num);251 heap_Print(heap,heap_data_num);252 253 heap_Init_Adjust(heap,heap_data_num);254 heap_Print(heap,heap_data_num);255 256 #endif257 258 #if 0259 heap_Insert(heap,&heap_data_num,1);260 heap_Insert(heap,&heap_data_num,3);261 heap_Insert(heap,&heap_data_num,11);262 heap_Insert(heap,&heap_data_num,5);263 heap_Insert(heap,&heap_data_num,4);264 heap_Insert(heap,&heap_data_num,8);265 heap_Insert(heap,&heap_data_num,7);266 heap_Insert(heap,&heap_data_num,6);267 268 heap_Print(heap,heap_data_num);269 270 heap_Delete(heap,&heap_data_num,8);271 272 heap_Print(heap,heap_data_num);273 #endif274 275 }