1 /* 2 ** Author: Eric Veach, July 1994. 3 ** 4 */ 5 6 #ifndef __priorityq_heap_h_ 7 #define __priorityq_heap_h_ 8 9 /* Use #define's so that another heap implementation can use this one */ 10 11 #define PQkey PQHeapKey 12 #define PQhandle PQHeapHandle 13 #define PriorityQ PriorityQHeap 14 15 #define pqNewPriorityQ(leq) __gl_pqHeapNewPriorityQ(leq) 16 #define pqDeletePriorityQ(pq) __gl_pqHeapDeletePriorityQ(pq) 17 18 /* The basic operations are insertion of a new key (pqInsert), 19 * and examination/extraction of a key whose value is minimum 20 * (pqMinimum/pqExtractMin). Deletion is also allowed (pqDelete); 21 * for this purpose pqInsert returns a "handle" which is supplied 22 * as the argument. 23 * 24 * An initial heap may be created efficiently by calling pqInsert 25 * repeatedly, then calling pqInit. In any case pqInit must be called 26 * before any operations other than pqInsert are used. 27 * 28 * If the heap is empty, pqMinimum/pqExtractMin will return a NULL key. 29 * This may also be tested with pqIsEmpty. 30 */ 31 #define pqInit(pq) __gl_pqHeapInit(pq) 32 #define pqInsert(pq, key) __gl_pqHeapInsert(pq, key) 33 #define pqMinimum(pq) __gl_pqHeapMinimum(pq) 34 #define pqExtractMin(pq) __gl_pqHeapExtractMin(pq) 35 #define pqDelete(pq, handle) __gl_pqHeapDelete(pq, handle) 36 #define pqIsEmpty(pq) __gl_pqHeapIsEmpty(pq) 37 38 /* Since we support deletion the data structure is a little more 39 * complicated than an ordinary heap. "nodes" is the heap itself; 40 * active nodes are stored in the range 1..pq->size. When the 41 * heap exceeds its allocated size (pq->max), its size doubles. 42 * The children of node i are nodes 2i and 2i+1. 43 * 44 * Each node stores an index into an array "handles". Each handle 45 * stores a key, plus a pointer back to the node which currently 46 * represents that key (ie. nodes[handles[i].node].handle == i). 47 */ 48 49 typedef void *PQkey; 50 typedef long PQhandle; 51 typedef struct PriorityQ PriorityQ; 52 53 typedef struct 54 { 55 PQhandle handle; 56 } PQnode; 57 typedef struct 58 { 59 PQkey key; 60 PQhandle node; 61 } PQhandleElem; 62 63 struct PriorityQ 64 { 65 PQnode *nodes; 66 PQhandleElem *handles; 67 long size, max; 68 PQhandle freeList; 69 int initialized; 70 int (*leq)(PQkey key1, PQkey key2); 71 }; 72 73 PriorityQ *pqNewPriorityQ(int (*leq)(PQkey key1, PQkey key2)); 74 void pqDeletePriorityQ(PriorityQ *pq); 75 76 void pqInit(PriorityQ *pq); 77 PQhandle pqInsert(PriorityQ *pq, PQkey key); 78 PQkey pqExtractMin(PriorityQ *pq); 79 void pqDelete(PriorityQ *pq, PQhandle handle); 80 81 #define __gl_pqHeapMinimum(pq) ((pq)->handles[(pq)->nodes[1].handle].key) 82 #define __gl_pqHeapIsEmpty(pq) ((pq)->size == 0) 83 84 #endif 85