1 | #ifndef BHEAP_H |
---|
2 | #define BHEAP_H |
---|
3 | /*** Header File for the Binary Heap Implementation ***/ |
---|
4 | /* |
---|
5 | * Shane Saunders |
---|
6 | */ |
---|
7 | #include "heap_info.h" /* Defines the universal heap structure type. */ |
---|
8 | |
---|
9 | /* This implementation stores the binary heap in a 1 dimensional array. */ |
---|
10 | |
---|
11 | /*** Structure Definitions ***/ |
---|
12 | |
---|
13 | /* Frontier set items in Dijkstra's algorithm stored in the binary heap |
---|
14 | * structure. |
---|
15 | */ |
---|
16 | typedef struct { |
---|
17 | int dirty; /* dirty flag if used for the lazy evaluation */ |
---|
18 | int item; /* edge number is used for the item. */ |
---|
19 | double key; /* distance is used as the key. */ |
---|
20 | } bheap_item_t; |
---|
21 | |
---|
22 | /* Binary heap structure for frontier set in Dijkstra's algorithm. |
---|
23 | * a[] - stores (distance, edge) pairs of the binary heap. |
---|
24 | * p[] - stores the positions of vertices in the binary heap a[]. |
---|
25 | * n - is the size of the binary heap. |
---|
26 | */ |
---|
27 | typedef struct { |
---|
28 | bheap_item_t *a; |
---|
29 | int *p; |
---|
30 | int n; |
---|
31 | long key_comps; |
---|
32 | } bheap_t; |
---|
33 | |
---|
34 | |
---|
35 | /*** Function prototypes. ***/ |
---|
36 | |
---|
37 | /* Binary heap functions. */ |
---|
38 | |
---|
39 | /* bh_alloc() allocates space for a binary heap of size n and initialises it. |
---|
40 | * Returns a pointer to the binary heap. |
---|
41 | */ |
---|
42 | bheap_t *bh_alloc(int n); |
---|
43 | |
---|
44 | /* bh_free() frees the space taken up by the binary heap pointed to by h. |
---|
45 | */ |
---|
46 | void bh_free(bheap_t *h); |
---|
47 | |
---|
48 | /* bh_min() returns the item with the minimum key in the binary heap pointed to |
---|
49 | * by h. |
---|
50 | */ |
---|
51 | int bh_min(bheap_t *h); |
---|
52 | |
---|
53 | /* bh_insert() inserts an item and its key value into the binary heap pointed |
---|
54 | * to by h. |
---|
55 | */ |
---|
56 | void bh_insert(bheap_t *h, int item, double key); |
---|
57 | |
---|
58 | /* bh_delete() deletes an item from the binary heap pointed to by h. |
---|
59 | */ |
---|
60 | void bh_delete(bheap_t *h, int item); |
---|
61 | /* bh_mark() marks an item from the binary heap pointed to by h. |
---|
62 | */ |
---|
63 | void bh_mark(bheap_t *h, int item, int flag); |
---|
64 | |
---|
65 | /* bh_get_key() returns the key value of an item from the binary heap pointed |
---|
66 | * to by h. |
---|
67 | */ |
---|
68 | double bh_get_key(bheap_t *h, int item); |
---|
69 | |
---|
70 | /* bh_is_dirty() returns the dirty value of an item from the binary heap pointed |
---|
71 | * to by h. |
---|
72 | */ |
---|
73 | int bh_is_dirty(bheap_t *h, int item); |
---|
74 | |
---|
75 | /* bh_decrease_key() decreases the value of 'item's key and then performs |
---|
76 | * sift-down until 'item' has been relocated to the correct position in the |
---|
77 | * binary heap. |
---|
78 | */ |
---|
79 | void bh_decrease_key(bheap_t *h, int item, double new_key); |
---|
80 | |
---|
81 | void bh_dump(bheap_t *h); |
---|
82 | |
---|
83 | /*** Alternative interface via the universal heap structure type. ***/ |
---|
84 | extern const heap_info_t BHEAP_info; |
---|
85 | |
---|
86 | |
---|
87 | #endif |
---|