1 |
/* RCSid $Id$ */ |
2 |
/* |
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 |