[983] | 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 { |
---|
[2090] | 17 | int dirty; /* dirty flag if used for the lazy evaluation */ |
---|
| 18 | int item; /* edge number is used for the item. */ |
---|
[983] | 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. |
---|
[2090] | 23 | * a[] - stores (distance, edge) pairs of the binary heap. |
---|
[983] | 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); |
---|
[2090] | 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); |
---|
[983] | 64 | |
---|
[2090] | 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 | |
---|
[983] | 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 |
---|