]>
Commit | Line | Data |
---|---|---|
8c23e0a4 DB |
1 | /* A Fibonacci heap datatype. |
2 | Copyright 1998, 1999, 2000, 2001 Free Software Foundation, Inc. | |
3 | Contributed by Daniel Berlin (dan@cgsoftware.com). | |
4 | ||
5 | This file is part of GNU CC. | |
6 | ||
7 | GNU CC is free software; you can redistribute it and/or modify it | |
8 | under the terms of the GNU General Public License as published by | |
9 | the Free Software Foundation; either version 2, or (at your option) | |
10 | any later version. | |
11 | ||
12 | GNU CC is distributed in the hope that it will be useful, but | |
13 | WITHOUT ANY WARRANTY; without even the implied warranty of | |
14 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU | |
15 | General Public License for more details. | |
16 | ||
17 | You should have received a copy of the GNU General Public License | |
18 | along with GNU CC; see the file COPYING. If not, write to | |
19 | the Free Software Foundation, 59 Temple Place - Suite 330, | |
20 | Boston, MA 02111-1307, USA. */ | |
21 | ||
22 | /* Fibonacci heaps are somewhat complex, but, there's an | |
23 | article in DDJ on them that explains them pretty well: | |
24 | ||
25 | http://www.ddj.com/articles/1997/9701/9701o/9701o.htm?topic=algoritms | |
26 | ||
27 | Introduction to algorithms by Corman and Rivest also goes over | |
28 | them. | |
29 | ||
30 | The original paper that introduced them is "Fibonacci heaps and their | |
31 | uses in improved network optimization algorithms" by Tarjan and | |
32 | Fredman (JACM 34(3), July 1987). | |
33 | ||
34 | Amortized and real worst case time for operations: | |
35 | ||
36 | ExtractMin: O(lg n) amortized. O(n) worst case. | |
37 | DecreaseKey: O(1) amortized. O(lg n) worst case. | |
38 | Insert: O(2) amortized. O(1) actual. | |
39 | Union: O(1) amortized. O(1) actual. | |
40 | ||
41 | ||
42 | */ | |
43 | ||
44 | #ifndef _FIBHEAP_H_ | |
45 | #define _FIBHEAP_H_ | |
46 | ||
47 | #include <ansidecl.h> | |
48 | ||
49 | typedef struct fibheap | |
50 | { | |
51 | size_t nodes; | |
52 | struct fibnode *min; | |
53 | struct fibnode *root; | |
54 | } *fibheap_t; | |
55 | typedef long fibheapkey_t; | |
56 | typedef struct fibnode | |
57 | { | |
58 | struct fibnode *parent; | |
59 | struct fibnode *child; | |
60 | struct fibnode *left; | |
61 | struct fibnode *right; | |
62 | unsigned int degree : sizeof(size_t) * CHAR_BIT - 2; | |
63 | unsigned int mark:1; | |
64 | fibheapkey_t key; | |
65 | void *data; | |
66 | } *fibnode_t; | |
67 | ||
68 | extern fibheap_t fibheap_new PARAMS ((void)); | |
69 | extern fibnode_t fibheap_insert PARAMS ((fibheap_t, fibheapkey_t, void *)); | |
70 | extern int fibheap_empty PARAMS ((fibheap_t)); | |
71 | extern fibheapkey_t fibheap_min_key PARAMS ((fibheap_t)); | |
72 | extern fibheapkey_t fibheap_replace_key PARAMS ((fibheap_t, fibnode_t, fibheapkey_t)); | |
73 | extern void *fibheap_replace_key_data PARAMS ((fibheap_t, fibnode_t, fibheapkey_t, void *)); | |
74 | extern void *fibheap_extract_min PARAMS ((fibheap_t)); | |
75 | extern void *fibheap_min PARAMS ((fibheap_t)); | |
76 | extern void *fibheap_replace_data PARAMS ((fibheap_t, fibnode_t, void *)); | |
77 | extern void *fibheap_delete_node PARAMS ((fibheap_t, fibnode_t)); | |
78 | extern void fibheap_delete PARAMS ((fibheap_t)); | |
79 | extern fibheap_t fibheap_union PARAMS ((fibheap_t, fibheap_t)); | |
80 | #endif /* _FIBHEAP_H_ */ |