posts - 1, comments - 0, trackbacks - 0

置顶随笔

c语言封装heap实现，废话不多说上代码

heap.h

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

heap.c

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