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 |