小顶堆---非递归C语言来一发

  1 #include <stdio.h>
  2 #include <stdlib.h>
  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 > heap_data_num / 2)
 64     {//leaf node can not move down
 65         return;
 66     }
 67 
 68     while(index <= heap_data_num / 2)
 69     {
 70         int child = index * 2; // left child 
 71 
 72         if(child > heap_data_num)
 73         { 
 74             return;
 75         }
 76 
 77         if(child < heap_data_num / 2)
 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_Insert
100  *
101  * purpose:
102  *     insert a value into heap and ajust heap struct
103  */
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 size
112     heap[*heap_data_num] = value; //add value to heap
113 
114     heap_Up(heap,*heap_data_num); //adjust heap struct
115 }
116 
117 /*
118  * name: heap_Delete
119  *
120  * purpost:
121  *     delete a value from heap
122  */
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 exist
137         return;
138     }
139 
140     heap[index] = heap[*heap_data_num]; //set the index value as final value
141     
142     (*heap_data_num)--;//the final value is not as the heap
143 
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 situation
149         heap_Up(heap,index);
150     }    
151     
152     heap[*heap_data_num + 1] = HEAP_FULL_VALUE; //delete final data
153 }
154 
155 void heap_Print(int heap[],int heap_data_num)
156 {
157     int i;
158     for(i = 1; i <= heap_data_num; i++)
159     {
160         printf("%d ",heap[i]);
161     }
162 
163     printf("\n");
164 }
165 
166 
167 int main()
168 {
169     int heap[HEAP_SIZE];        
170     int i,heap_data_num = 0;
171 
172     for(i = 0; i < heap_data_num; i++)
173     {
174         heap[i] = HEAP_FULL_VALUE;
175     }
176     
177 #if 0
178     heap_Insert(heap,&heap_data_num,1);
179     heap_Insert(heap,&heap_data_num,3);
180     heap_Insert(heap,&heap_data_num,4);
181     heap_Insert(heap,&heap_data_num,5);
182     heap_Insert(heap,&heap_data_num,8);
183     heap_Insert(heap,&heap_data_num,2);
184     heap_Insert(heap,&heap_data_num,7);
185     heap_Insert(heap,&heap_data_num,6);
186 
187     heap_Print(heap,heap_data_num);
188     
189     heap_Delete(heap,&heap_data_num,2);
190     heap_Print(heap,heap_data_num);
191     heap_Delete(heap,&heap_data_num,1);
192     heap_Print(heap,heap_data_num);
193     
194 #endif
195 
196 #if 1
197     heap_Insert(heap,&heap_data_num,1);
198     heap_Insert(heap,&heap_data_num,3);
199     heap_Insert(heap,&heap_data_num,11);
200     heap_Insert(heap,&heap_data_num,5);
201     heap_Insert(heap,&heap_data_num,4);
202     heap_Insert(heap,&heap_data_num,8);
203     heap_Insert(heap,&heap_data_num,7);
204     heap_Insert(heap,&heap_data_num,6);
205 
206     heap_Print(heap,heap_data_num);
207     
208     heap_Delete(heap,&heap_data_num,8);
209 
210     heap_Print(heap,heap_data_num);
211 #endif
212 
213 }