heap.h
1 /*
2  * Player - One Hell of a Robot Server
3  * Copyright (C) 2008-
4  * Brian Gerkey gerkey@willowgarage.com
5  *
6  *
7  * This library is free software; you can redistribute it and/or
8  * modify it under the terms of the GNU Lesser General Public
9  * License as published by the Free Software Foundation; either
10  * version 2.1 of the License, or (at your option) any later version.
11  *
12  * This library is distributed in the hope that it will be useful,
13  * but WITHOUT ANY WARRANTY; without even the implied warranty of
14  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
15  * Lesser General Public License for more details.
16  *
17  * You should have received a copy of the GNU Lesser General Public
18  * License along with this library; if not, write to the Free Software
19  * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
20  */
21 
22 /*
23  * An implementation of a heap, as seen in "Introduction to Algorithms," by
24  * Cormen, Leiserson, and Rivest, pages 140-152.
25  */
26 
27 #ifndef _HEAP_H_
28 #define _HEAP_H_
29 
30 #define HEAP_PARENT(i) ((i)/2)
31 #define HEAP_LEFT(i) (2*(i))
32 #define HEAP_RIGHT(i) (2*(i)+1)
33 
34 #ifdef __cplusplus
35 extern "C" {
36 #endif
37 
38 struct heap;
39 
40 typedef void (*heap_free_elt_fn_t) (void* elt);
41 
42 typedef struct heap
43 {
44  int len;
45  int size;
46  heap_free_elt_fn_t free_fn;
47  double* A;
48  void** data;
49 } heap_t;
50 
51 heap_t* heap_alloc(int size, heap_free_elt_fn_t free_fn);
52 void heap_free(heap_t* h);
53 void heap_heapify(heap_t* h, int i);
54 void* heap_extract_max(heap_t* h);
55 void heap_insert(heap_t* h, double key, void* data);
56 void heap_dump(heap_t* h);
57 int heap_valid(heap_t* h);
58 int heap_empty(heap_t* h);
59 void heap_reset(heap_t* h);
60 
61 #ifdef __cplusplus
62 }
63 #endif
64 
65 #endif

Last updated 12 September 2005 21:38:45