File indexing completed on 2024-04-28 07:32:05
0001 /* 0002 ** Author: Eric Veach, July 1994. 0003 ** 0004 */ 0005 0006 #ifndef __priorityq_heap_h_ 0007 #define __priorityq_heap_h_ 0008 0009 /* Use #define's so that another heap implementation can use this one */ 0010 0011 #define PQkey PQHeapKey 0012 #define PQhandle PQHeapHandle 0013 #define PriorityQ PriorityQHeap 0014 0015 #define pqNewPriorityQ(leq) __gl_pqHeapNewPriorityQ(leq) 0016 #define pqDeletePriorityQ(pq) __gl_pqHeapDeletePriorityQ(pq) 0017 0018 /* The basic operations are insertion of a new key (pqInsert), 0019 * and examination/extraction of a key whose value is minimum 0020 * (pqMinimum/pqExtractMin). Deletion is also allowed (pqDelete); 0021 * for this purpose pqInsert returns a "handle" which is supplied 0022 * as the argument. 0023 * 0024 * An initial heap may be created efficiently by calling pqInsert 0025 * repeatedly, then calling pqInit. In any case pqInit must be called 0026 * before any operations other than pqInsert are used. 0027 * 0028 * If the heap is empty, pqMinimum/pqExtractMin will return a NULL key. 0029 * This may also be tested with pqIsEmpty. 0030 */ 0031 #define pqInit(pq) __gl_pqHeapInit(pq) 0032 #define pqInsert(pq, key) __gl_pqHeapInsert(pq, key) 0033 #define pqMinimum(pq) __gl_pqHeapMinimum(pq) 0034 #define pqExtractMin(pq) __gl_pqHeapExtractMin(pq) 0035 #define pqDelete(pq, handle) __gl_pqHeapDelete(pq, handle) 0036 #define pqIsEmpty(pq) __gl_pqHeapIsEmpty(pq) 0037 0038 /* Since we support deletion the data structure is a little more 0039 * complicated than an ordinary heap. "nodes" is the heap itself; 0040 * active nodes are stored in the range 1..pq->size. When the 0041 * heap exceeds its allocated size (pq->max), its size doubles. 0042 * The children of node i are nodes 2i and 2i+1. 0043 * 0044 * Each node stores an index into an array "handles". Each handle 0045 * stores a key, plus a pointer back to the node which currently 0046 * represents that key (ie. nodes[handles[i].node].handle == i). 0047 */ 0048 0049 typedef void *PQkey; 0050 typedef long PQhandle; 0051 typedef struct PriorityQ PriorityQ; 0052 0053 typedef struct 0054 { 0055 PQhandle handle; 0056 } PQnode; 0057 typedef struct 0058 { 0059 PQkey key; 0060 PQhandle node; 0061 } PQhandleElem; 0062 0063 struct PriorityQ 0064 { 0065 PQnode *nodes; 0066 PQhandleElem *handles; 0067 long size, max; 0068 PQhandle freeList; 0069 int initialized; 0070 int (*leq)(PQkey key1, PQkey key2); 0071 }; 0072 0073 PriorityQ *pqNewPriorityQ(int (*leq)(PQkey key1, PQkey key2)); 0074 void pqDeletePriorityQ(PriorityQ *pq); 0075 0076 void pqInit(PriorityQ *pq); 0077 PQhandle pqInsert(PriorityQ *pq, PQkey key); 0078 PQkey pqExtractMin(PriorityQ *pq); 0079 void pqDelete(PriorityQ *pq, PQhandle handle); 0080 0081 #define __gl_pqHeapMinimum(pq) ((pq)->handles[(pq)->nodes[1].handle].key) 0082 #define __gl_pqHeapIsEmpty(pq) ((pq)->size == 0) 0083 0084 #endif