[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 { |
---|
| 17 | int item; /* vertex number is used for the item. */ |
---|
| 18 | double key; /* distance is used as the key. */ |
---|
| 19 | } bheap_item_t; |
---|
| 20 | |
---|
| 21 | /* Binary heap structure for frontier set in Dijkstra's algorithm. |
---|
| 22 | * a[] - stores (distance, vertex) pairs of the binary heap. |
---|
| 23 | * p[] - stores the positions of vertices in the binary heap a[]. |
---|
| 24 | * n - is the size of the binary heap. |
---|
| 25 | */ |
---|
| 26 | typedef struct { |
---|
| 27 | bheap_item_t *a; |
---|
| 28 | int *p; |
---|
| 29 | int n; |
---|
| 30 | long key_comps; |
---|
| 31 | } bheap_t; |
---|
| 32 | |
---|
| 33 | |
---|
| 34 | /*** Function prototypes. ***/ |
---|
| 35 | |
---|
| 36 | /* Binary heap functions. */ |
---|
| 37 | |
---|
| 38 | /* bh_alloc() allocates space for a binary heap of size n and initialises it. |
---|
| 39 | * Returns a pointer to the binary heap. |
---|
| 40 | */ |
---|
| 41 | bheap_t *bh_alloc(int n); |
---|
| 42 | |
---|
| 43 | /* bh_free() frees the space taken up by the binary heap pointed to by h. |
---|
| 44 | */ |
---|
| 45 | void bh_free(bheap_t *h); |
---|
| 46 | |
---|
| 47 | /* bh_min() returns the item with the minimum key in the binary heap pointed to |
---|
| 48 | * by h. |
---|
| 49 | */ |
---|
| 50 | int bh_min(bheap_t *h); |
---|
| 51 | |
---|
| 52 | /* bh_insert() inserts an item and its key value into the binary heap pointed |
---|
| 53 | * to by h. |
---|
| 54 | */ |
---|
| 55 | void bh_insert(bheap_t *h, int item, double key); |
---|
| 56 | |
---|
| 57 | /* bh_delete() deletes an item from the binary heap pointed to by h. |
---|
| 58 | */ |
---|
| 59 | void bh_delete(bheap_t *h, int item); |
---|
| 60 | |
---|
| 61 | /* bh_decrease_key() decreases the value of 'item's key and then performs |
---|
| 62 | * sift-down until 'item' has been relocated to the correct position in the |
---|
| 63 | * binary heap. |
---|
| 64 | */ |
---|
| 65 | void bh_decrease_key(bheap_t *h, int item, double new_key); |
---|
| 66 | |
---|
| 67 | void bh_dump(bheap_t *h); |
---|
| 68 | |
---|
| 69 | /*** Alternative interface via the universal heap structure type. ***/ |
---|
| 70 | extern const heap_info_t BHEAP_info; |
---|
| 71 | |
---|
| 72 | |
---|
| 73 | #endif |
---|