1 /*
 2  * heap.h
 3  *
 4  *  Created on: 2012-8-29
 5  *      Author: aHuJever
 6  */
 7 
 8 #ifndef BINARY_HEAP_H_
 9 #define BINARY_HEAP_H_
10 #ifdef __cplusplus
11     extern "C" {
12 #endif
13 
14     typedef void* HeapElement;
15 
16     typedef int (*HeapElementCmp)(HeapElement a, HeapElement b);
17 
18     typedef struct _BinaryHeap BinaryHeap;
19 
20     BinaryHeap *CreateBinaryHeap(HeapElementCmp cmp);
21 
22     int push(BinaryHeap* heap, HeapElement value);
23 
24     HeapElement pop(BinaryHeap* heap);
25 
26     HeapElement top(BinaryHeap* heap);
27 
28     void BinaryHeapFree(BinaryHeap* heap);
29 
30 #ifdef __cplusplus
31 }
32 #endif
33 #endif /* HEAP_H_ */
34 

  1 /*
  2  * heap.h
  3  *
  4  *  Created on: 2012-8-29
  5  *      Author: aHuJever
  6  */
  7 #include <stdlib.h>
  8 #include "heap.h"
  9 
 10 typedef struct _BinaryHeap{
 11 
 12     int element_num;
 13 
 14     int alloced_size;
 15 
 16     HeapElement* heapvalue;
 17 
 18     int (*HeapCmpFun)(HeapElement a, HeapElement b);
 19 
 20 };
 21 
 22 BinaryHeap *CreateBinaryHeap(HeapElementCmp cmp){
 23 
 24     BinaryHeap *heap = malloc(sizeof(BinaryHeap));
 25 
 26     if(heap == NULL){
 27         return NULL;
 28     }
 29     heap->alloced_size = 16;
 30     heap->element_num = 0;
 31     heap->HeapCmpFun = cmp;
 32     heap->heapvalue = malloc(sizeof(HeapElement) * heap->alloced_size);
 33     if(heap->heapvalue == NULL) {
 34         free(heap);
 35         return NULL;
 36     }
 37     return heap;
 38 }
 39 
 40 
 41 int push(BinaryHeap* heap, HeapElement value){
 42 
 43     if(heap->element_num == heap->alloced_size){
 44         heap->alloced_size *= 2;
 45         HeapElement* newValue = realloc(heap->heapvalue, sizeof(HeapElement) * heap->alloced_size);
 46         if(newValue == NULL)     return -1;
 47         heap->heapvalue = newValue;
 48     }
 49     heap->heapvalue[heap->element_num] = value;
 50     heap->element_num ++;
 51     shift_up(heap, value);
 52     return 0;
 53 }
 54 
 55 
 56 HeapElement pop(BinaryHeap* heap){
 57 
 58     if(heap->element_num == 0)    return NULL;
 59     int num = heap->element_num;
 60     HeapElement ret = heap->heapvalue[0];
 61     heap->heapvalue[0] = heap->heapvalue[num-1];
 62     heap->element_num--;
 63     if(heap->element_num != 0)
 64     {
 65         shift_down(heap, 0);
 66     }
 67 
 68     return ret;
 69 }
 70 
 71 void BinaryHeapFree(BinaryHeap* heap){
 72     if(heap != NULL){
 73         free(heap->heapvalue);
 74         free(heap);
 75     }
 76 
 77 }
 78 
 79 int shift_up(BinaryHeap* heap, HeapElement value){
 80 
 81     int current = heap->element_num-1;
 82     while(current > 0){
 83         int parent = getparent(current);
 84         if(heap->HeapCmpFun(heap->heapvalue[current], heap->heapvalue[parent]) < 0){
 85             swap(heap, current, parent);
 86             current = parent;
 87         } else{
 88             return 0;
 89         }
 90     }
 91     return 0;
 92 }
 93 
 94 int shift_down(BinaryHeap* heap, int index){
 95 
 96     if(heap->element_num == 0)    return 0;
 97 
 98     int current = index;
 99     int left;
100     int right;
101     while(current < heap->element_num){
102         left = (current << 1) + 1;
103         right = (current << 1) + 2;
104 
105         if(left >= heap->element_num && right >= heap->element_num){
106             return 0;
107         } else if(left < heap->element_num && right >= heap->element_num){
108 
109         } else if(left < heap->element_num && right < heap->element_num){
110             if(heap->HeapCmpFun(heap->heapvalue[left], heap->heapvalue[right]) >= 0){
111                 int temp = left;
112                 left = right;
113                 right = temp;
114             }
115         }
116         if(heap->HeapCmpFun(heap->heapvalue[left], heap->heapvalue[current]) < 0){
117             swap(heap, left, current);
118             current = left;
119         } else{
120             return 0;
121         }
122     }
123     return 0;
124 }
125 
126 int getparent(int index){
127 
128     return (index - 1) >> 1;
129 }
130 
131 int getrightchild(int index){
132 
133     return (index << 1) + 2;
134 }
135 
136 int getlefchild(int index){
137 
138     return (index << 1) + 1;
139 }
140 
141 void swap(BinaryHeap* heap, int index1, int index2){
142 
143     HeapElement temp = heap->heapvalue[index1];
144     heap->heapvalue[index1] = heap->heapvalue[index2];
145     heap->heapvalue[index2] = temp;
146 
147 }
148 

stone1342006 2012-09-12 21:57 发表评论