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