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 |
---|