fheap.h (4856B)
1 #ifndef FHEAP_H 2 #define FHEAP_H 3 4 #include <assert.h> 5 #include <stdint.h> 6 #include <stdlib.h> 7 #include <string.h> 8 9 typedef struct fnode_struct { 10 uint64_t value; 11 void *data; 12 13 struct fnode_struct *parent; 14 struct fnode_struct *children; 15 size_t nchildren; 16 uint64_t marked; 17 18 struct fnode_struct *left; 19 struct fnode_struct *right; 20 } fnode_t; 21 22 typedef struct { 23 size_t n; 24 fnode_t *min; 25 fnode_t *head; 26 } fheap_t; 27 28 /** 29 * Intialise a Fibonacci heap node 30 * 31 * Initialises a new node. Internally in the heap all elements should be 32 * represented as a fnode_t. The two members value and data corresponds 33 * to the "key" (by which we order the elements) and the "data" (some 34 * associated data we want to represent). 35 * 36 * Note that the memory position for node already has to be allocated 37 * (usually this is done by fheap_insert). 38 * 39 * @param node pointer to the fnode_t to initialise 40 * @param value the "key"/"value" to give it 41 * @param data pointer to some associated data 42 */ 43 void fnode_init(fnode_t *node, const uint64_t value, void *data); 44 45 /** 46 * Clear a Fibonacci heap node 47 * 48 * Removes a node, and frees it recursively (i.e. both the node itself 49 * and all its children are cleared, and the allocated memory is freed). 50 * 51 * @param node pointer to the node to free 52 */ 53 void fnode_clear(fnode_t *node); 54 55 /** 56 * Initialise a Fibonacci heap 57 * 58 * The heap will be initialised to an empty heap. 59 * 60 * @param heap pointer to the heap to initialise 61 */ 62 void fheap_init(fheap_t *heap); 63 64 /** 65 * Clear a Fibonacci heap 66 * 67 * Clear a Fibonacci heap. All remaining inserted elements will be freed 68 * recursively. 69 * 70 * @param heap pointer to the heap to clear 71 */ 72 void fheap_clear(fheap_t *heap); 73 74 /** 75 * Insert a (value, data) pair into a Fibonacci heap 76 * 77 * Inserts a (value, data) pair into a Fibonacci heap, and allocates a 78 * new fnode_t element for them. This will allocate memory for the node, 79 * which will have to be cleared. The function returns a pointer to the 80 * new fnode_t (so we can access it directly, update its value etc.) 81 * 82 * Note! 83 * This will fail (hard) if value is UINT64_MAX and data is a NULL 84 * pointer. This is a forbidden (value, data) pair! 85 * 86 * @param heap pointer to the heap to insert into 87 * @param value the value (aka. key) to insert 88 * @param data pointer to associated data of this node 89 * @returns pointer to the new fnode_t created 90 */ 91 fnode_t *fheap_insert(fheap_t *heap, const uint64_t value, void *data); 92 93 /** 94 * Extract minimum node of a Fibonacci heap 95 * 96 * Extracts the minimum node of a Fibonacci heap. Note that this returns 97 * the pointer to this node, but does not deallocate it (which makes it 98 * possible to work with the node before deallocating it). It needs to 99 * be deallocated manually (because it is no longer in the heap). If the 100 * heap is empty a NULL pointer is returned. 101 * 102 * @param heap the heap to remove the minimum node from 103 */ 104 fnode_t *fheap_extract_min_node(fheap_t *heap); 105 106 /** 107 * Extract minimum from a Fibonacci heap 108 * 109 * Extracts the minimum value in a heap (and removing this value from 110 * the heap). This function then deallocates the fnode_t (only this 111 * node). The value of the minimum node is returned, and the address to 112 * which *data points is set to the address of the associated data of 113 * the node. If the heap is empty this returns UINT64_MAX and sets *data 114 * to NULL; 115 * 116 * @param data 117 * pointer to pointer (address) to associated data, which we want to 118 * set to the pointer to the associated data of the node, i.e. *data 119 * will be set to member .data of extracted minimum 120 * @param heap 121 * pointer to the heap to extract minimum from 122 * @returns 123 * the value ("key") associated with the extracted minimum 124 */ 125 uint64_t fheap_extract_min(void **data, fheap_t *heap); 126 127 /** 128 * Decerease value of a node in a Fibonacci heap 129 * 130 * Decreases the value of a node in a Fibonacci heap. This will reorder 131 * the heap appropriately to and update its minimum if neccessary. 132 * 133 * Note! 134 * Unexpected behaviour may occur if value is greater than the previous 135 * value in the node. This is not checked for and will probably mess up 136 * the whole Fibonacci heap. If not sure, check before using this 137 * function. 138 * 139 * @param heap the heap in which we find the node 140 * @param node the node to decrease the value of 141 * @param value the new value of the node 142 */ 143 void fheap_decrease_value(fheap_t *heap, fnode_t *node, const uint64_t value); 144 145 /** 146 * Deletes a node from a Fibonacci heap 147 * 148 * Deletes a node from a Fibonacci heap, freeing and clearing as 149 * neccessary. This assumes that node actually points to a node in the 150 * Fibonacci heap, so in particular node is not NULL and heap is not an 151 * empty heap. 152 * 153 * @param heap the heap to remove node from 154 * @param node the node to delete 155 */ 156 void fheap_delete(fheap_t *heap, fnode_t *node); 157 158 #endif