1 /*====================================================================* 2 - Copyright (C) 2001 Leptonica. All rights reserved. 3 - This software is distributed in the hope that it will be 4 - useful, but with NO WARRANTY OF ANY KIND. 5 - No author or distributor accepts responsibility to anyone for the 6 - consequences of using this software, or for whether it serves any 7 - particular purpose or works at all, unless he or she says so in 8 - writing. Everyone is granted permission to copy, modify and 9 - redistribute this source code, for commercial or non-commercial 10 - purposes, with the following restrictions: (1) the origin of this 11 - source code must not be misrepresented; (2) modified versions must 12 - be plainly marked as such; and (3) this notice may not be removed 13 - or altered from any source or modified source distribution. 14 *====================================================================*/ 15 16 #ifndef LEPTONICA_HEAP_H 17 #define LEPTONICA_HEAP_H 18 19 /* 20 * heap.h 21 * 22 * Expandable priority queue configured as a heap for arbitrary void* data 23 * 24 * The L_Heap is used to implement a priority queue. The elements 25 * in the heap are ordered in either increasing or decreasing key value. 26 * The key is a float field 'keyval' that is required to be 27 * contained in the elements of the queue. 28 * 29 * The heap is a simple binary tree with the following constraints: 30 * - the key of each node is >= the keys of the two children 31 * - the tree is complete, meaning that each level (1, 2, 4, ...) 32 * is filled and the last level is filled from left to right 33 * 34 * The tree structure is implicit in the queue array, with the 35 * array elements numbered as a breadth-first search of the tree 36 * from left to right. It is thus guaranteed that the largest 37 * (or smallest) key belongs to the first element in the array. 38 * 39 * Heap sort is used to sort the array. Once an array has been 40 * sorted as a heap, it is convenient to use it as a priority queue, 41 * because the min (or max) elements are always at the root of 42 * the tree (element 0), and once removed, the heap can be 43 * resorted in not more than log[n] steps, where n is the number 44 * of elements on the heap. Likewise, if an arbitrary element is 45 * added to the end of the array A, the sorted heap can be restored 46 * in not more than log[n] steps. 47 * 48 * A L_Heap differs from a L_Queue in that the elements in the former 49 * are sorted by a key. Internally, the array is maintained 50 * as a queue, with a pointer to the end of the array. The 51 * head of the array always remains at array[0]. The array is 52 * maintained (sorted) as a heap. When an item is removed from 53 * the head, the last item takes its place (thus reducing the 54 * array length by 1), and this is followed by array element 55 * swaps to restore the heap property. When an item is added, 56 * it goes at the end of the array, and is swapped up to restore 57 * the heap. If the ptr array is full, adding another item causes 58 * the ptr array size to double. 59 * 60 * For further implementation details, see heap.c. 61 */ 62 63 struct L_Heap 64 { 65 l_int32 nalloc; /* size of allocated ptr array */ 66 l_int32 n; /* number of elements stored in the heap */ 67 void **array; /* ptr array */ 68 l_int32 direction; /* L_SORT_INCREASING or L_SORT_DECREASING */ 69 }; 70 typedef struct L_Heap L_HEAP; 71 72 73 #endif /* LEPTONICA_HEAP_H */ 74