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., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 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
35extern "C" {
36#endif
37
38struct heap;
39
40typedef void (*heap_free_elt_fn_t) (void* elt);
41
42typedef 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
51heap_t* heap_alloc(int size, heap_free_elt_fn_t free_fn);
52void heap_free(heap_t* h);
53void heap_heapify(heap_t* h, int i);
54void* heap_extract_max(heap_t* h);
55void heap_insert(heap_t* h, double key, void* data);
56void heap_dump(heap_t* h);
57int heap_valid(heap_t* h);
58int heap_empty(heap_t* h);
59void heap_reset(heap_t* h);
60
61#ifdef __cplusplus
62}
63#endif
64
65#endif
Definition heap.h:43