Leptonica 1.68
C Image Processing Library

heap.h

Go to the documentation of this file.
00001 /*====================================================================*
00002  -  Copyright (C) 2001 Leptonica.  All rights reserved.
00003  -  This software is distributed in the hope that it will be
00004  -  useful, but with NO WARRANTY OF ANY KIND.
00005  -  No author or distributor accepts responsibility to anyone for the
00006  -  consequences of using this software, or for whether it serves any
00007  -  particular purpose or works at all, unless he or she says so in
00008  -  writing.  Everyone is granted permission to copy, modify and
00009  -  redistribute this source code, for commercial or non-commercial
00010  -  purposes, with the following restrictions: (1) the origin of this
00011  -  source code must not be misrepresented; (2) modified versions must
00012  -  be plainly marked as such; and (3) this notice may not be removed
00013  -  or altered from any source or modified source distribution.
00014  *====================================================================*/
00015 
00016 #ifndef  LEPTONICA_HEAP_H
00017 #define  LEPTONICA_HEAP_H
00018 
00019 /*
00020  *  heap.h
00021  *
00022  *      Expandable priority queue configured as a heap for arbitrary void* data
00023  *
00024  *      The L_Heap is used to implement a priority queue.  The elements
00025  *      in the heap are ordered in either increasing or decreasing key value.
00026  *      The key is a float field 'keyval' that is required to be
00027  *      contained in the elements of the queue.
00028  * 
00029  *      The heap is a simple binary tree with the following constraints:
00030  *         - the key of each node is >= the keys of the two children
00031  *         - the tree is complete, meaning that each level (1, 2, 4, ...)
00032  *           is filled and the last level is filled from left to right
00033  *
00034  *      The tree structure is implicit in the queue array, with the
00035  *      array elements numbered as a breadth-first search of the tree
00036  *      from left to right.  It is thus guaranteed that the largest
00037  *      (or smallest) key belongs to the first element in the array.
00038  *
00039  *      Heap sort is used to sort the array.  Once an array has been
00040  *      sorted as a heap, it is convenient to use it as a priority queue,
00041  *      because the min (or max) elements are always at the root of
00042  *      the tree (element 0), and once removed, the heap can be
00043  *      resorted in not more than log[n] steps, where n is the number
00044  *      of elements on the heap.  Likewise, if an arbitrary element is
00045  *      added to the end of the array A, the sorted heap can be restored
00046  *      in not more than log[n] steps.
00047  *
00048  *      A L_Heap differs from a L_Queue in that the elements in the former
00049  *      are sorted by a key.  Internally, the array is maintained
00050  *      as a queue, with a pointer to the end of the array.  The
00051  *      head of the array always remains at array[0].  The array is
00052  *      maintained (sorted) as a heap.  When an item is removed from
00053  *      the head, the last item takes its place (thus reducing the
00054  *      array length by 1), and this is followed by array element
00055  *      swaps to restore the heap property.   When an item is added,
00056  *      it goes at the end of the array, and is swapped up to restore
00057  *      the heap.  If the ptr array is full, adding another item causes
00058  *      the ptr array size to double.
00059  *      
00060  *      For further implementation details, see heap.c.
00061  */
00062 
00063 struct L_Heap
00064 {
00065     l_int32      nalloc;      /* size of allocated ptr array                 */
00066     l_int32      n;           /* number of elements stored in the heap       */
00067     void       **array;       /* ptr array                                   */
00068     l_int32      direction;   /* L_SORT_INCREASING or L_SORT_DECREASING      */
00069 };
00070 typedef struct L_Heap  L_HEAP;
00071 
00072 
00073 #endif  /* LEPTONICA_HEAP_H */
 All Data Structures Files Functions Variables Typedefs Enumerations Enumerator Defines