1 |
greg |
2.1 |
/* |
2 |
|
|
** Author: Christian Reetz ([email protected]) |
3 |
|
|
*/ |
4 |
|
|
#ifndef __MAXHEAP_H |
5 |
|
|
#define __MAXHEAP_H |
6 |
|
|
|
7 |
|
|
#ifdef __cplusplus |
8 |
|
|
extern "C" { |
9 |
|
|
#endif |
10 |
|
|
|
11 |
|
|
#include "g3vector.h" |
12 |
|
|
|
13 |
|
|
#define HP_STARTCAP 5000001 |
14 |
|
|
|
15 |
|
|
#define HP_INVALID 0 |
16 |
|
|
#define HP_BUILD 1 |
17 |
|
|
#define HP_SORTED 2 |
18 |
|
|
|
19 |
|
|
typedef struct heapElem { |
20 |
|
|
g3Float key; |
21 |
|
|
void* entity; |
22 |
|
|
} heapElem; |
23 |
|
|
|
24 |
|
|
typedef struct maxHeap { |
25 |
|
|
int size; |
26 |
|
|
int cap; |
27 |
|
|
int state; |
28 |
|
|
heapElem* heap; |
29 |
|
|
} maxHeap; |
30 |
|
|
|
31 |
|
|
#define mheap_get_max(hp) (hp->heap[0]) |
32 |
|
|
#define mh_left(i) (2*i + 1) |
33 |
|
|
#define mh_right(i) (2*i + 2) |
34 |
|
|
#define mh_parent(i) (((int) ((i + 1)/2)) - 1) |
35 |
|
|
|
36 |
|
|
int mheap_init(maxHeap* hp); |
37 |
|
|
void mheap_free(maxHeap* hp); |
38 |
|
|
maxHeap* mheap_create(); |
39 |
|
|
void mheap_build(maxHeap* hp); |
40 |
|
|
void mheap_sort(maxHeap* hp); |
41 |
|
|
|
42 |
|
|
heapElem mheap_remove_max(maxHeap* hp); |
43 |
|
|
int mheap_insert(maxHeap* hp,g3Float key,void* entity); |
44 |
|
|
|
45 |
|
|
|
46 |
|
|
#ifdef __cplusplus |
47 |
|
|
} |
48 |
|
|
#endif |
49 |
|
|
|
50 |
|
|
#endif |