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