heap.h
00001 /*
00002  *  Player - One Hell of a Robot Server
00003  *  Copyright (C) 2008-
00004  *     Brian Gerkey gerkey@willowgarage.com
00005  *                      
00006  *
00007  *  This library is free software; you can redistribute it and/or
00008  *  modify it under the terms of the GNU Lesser General Public
00009  *  License as published by the Free Software Foundation; either
00010  *  version 2.1 of the License, or (at your option) any later version.
00011  *
00012  *  This library is distributed in the hope that it will be useful,
00013  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
00014  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
00015  *  Lesser General Public License for more details.
00016  *
00017  *  You should have received a copy of the GNU Lesser General Public
00018  *  License along with this library; if not, write to the Free Software
00019  *  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
00020  */
00021 
00022 /*
00023  * An implementation of a heap, as seen in "Introduction to Algorithms," by
00024  * Cormen, Leiserson, and Rivest, pages 140-152.
00025  */
00026 
00027 #ifndef _HEAP_H_
00028 #define _HEAP_H_
00029 
00030 #define HEAP_PARENT(i) ((i)/2)
00031 #define HEAP_LEFT(i) (2*(i))
00032 #define HEAP_RIGHT(i) (2*(i)+1)
00033 
00034 #ifdef __cplusplus
00035 extern "C" {
00036 #endif
00037 
00038 struct heap;
00039 
00040 typedef void (*heap_free_elt_fn_t) (void* elt);
00041 
00042 typedef struct heap
00043 {
00044   int len;
00045   int size;
00046   heap_free_elt_fn_t free_fn;
00047   double* A;
00048   void** data;
00049 } heap_t;
00050 
00051 heap_t* heap_alloc(int size, heap_free_elt_fn_t free_fn);
00052 void heap_free(heap_t* h);
00053 void heap_heapify(heap_t* h, int i);
00054 void* heap_extract_max(heap_t* h);
00055 void heap_insert(heap_t* h, double key, void* data);
00056 void heap_dump(heap_t* h);
00057 int heap_valid(heap_t* h);
00058 int heap_empty(heap_t* h);
00059 void heap_reset(heap_t* h);
00060 
00061 #ifdef __cplusplus
00062 }
00063 #endif
00064 
00065 #endif

Last updated 12 September 2005 21:38:45