00001 /* quickHeap - Heap implemented as an array for speed. 00002 * 00003 * This file is copyright 2002 Jim Kent, but license is hereby 00004 * granted for all use - public, private or commercial. 00005 * 00006 * The array can be resized as it grows. 00007 * By preserving the relationship that the children of n are at 2n+1 and 2n+2, 00008 * and therefore the parent of n is at (n-1)/2, we can save alot of pointer 00009 * manipulation and get some speed. 00010 * This routine could for instance be used at the heart of a multi-way mergesort 00011 * or other situation such as a priority queue. 00012 * 00013 */ 00014 00015 struct quickHeap 00016 /* A quick array heap. */ 00017 { 00018 void **heap; 00019 int heapCount; 00020 int heapMax; 00021 int (*compareFunc)(const void *elem1, const void *elem2); 00022 }; 00023 00024 struct quickHeap *newQuickHeap(int initSize, 00025 int (*compare )(const void *elem1, const void *elem2)); 00026 /* Create a new array quick heap of initial size specified, 00027 * The compare function must return > 0 if elem1 > elem2, etc.*/ 00028 00029 void freeQuickHeap(struct quickHeap **pH); 00030 /* Heap needs more space, double the size of the array preserving elements */ 00031 00032 void addToQuickHeap(struct quickHeap *h, void *elem); 00033 /* add to heap at end (expands array if needed), rebalance */ 00034 00035 void quickHeapTopChanged(struct quickHeap *h); 00036 /* only the value of the top element has changed, now rebalance */ 00037 00038 boolean quickHeapEmpty(struct quickHeap *h); 00039 /* return TRUE if quick heap is empty, otherwise FALSE */ 00040 00041 boolean removeFromQuickHeapByElem(struct quickHeap *h, void *elem); 00042 /* Do a linear search in heap array for elem, 00043 * then remove it by position n. Return TRUE 00044 * if found and removed, otherwise return FALSE. */ 00045 00046 void *peekQuickHeapTop(struct quickHeap *h); 00047 /* return the top element or NULL if empty */ 00048 00049 void *removeQuickHeapTop(struct quickHeap *h); 00050 /* Return elem (pointer) in heap array[0] 00051 * which will be NULL if heap is empty. 00052 * Then that top element if found is removed. */ 00053
1.5.2