1169695Skan/* A Fibonacci heap datatype. 2169695Skan Copyright 1998, 1999, 2000, 2001, 2002 Free Software Foundation, Inc. 3169695Skan Contributed by Daniel Berlin (dan@cgsoftware.com). 4169695Skan 5169695SkanThis file is part of GCC. 6169695Skan 7169695SkanGCC is free software; you can redistribute it and/or modify it 8169695Skanunder the terms of the GNU General Public License as published by 9169695Skanthe Free Software Foundation; either version 2, or (at your option) 10169695Skanany later version. 11169695Skan 12169695SkanGCC is distributed in the hope that it will be useful, but 13169695SkanWITHOUT ANY WARRANTY; without even the implied warranty of 14169695SkanMERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 15169695SkanGeneral Public License for more details. 16169695Skan 17169695SkanYou should have received a copy of the GNU General Public License 18169695Skanalong with GCC; see the file COPYING. If not, write to 19169695Skanthe Free Software Foundation, 51 Franklin Street - Fifth Floor, 20169695SkanBoston, MA 02110-1301, USA. */ 21169695Skan 22169695Skan/* Fibonacci heaps are somewhat complex, but, there's an article in 23169695Skan DDJ that explains them pretty well: 24169695Skan 25169695Skan http://www.ddj.com/articles/1997/9701/9701o/9701o.htm?topic=algoritms 26169695Skan 27169695Skan Introduction to algorithms by Corman and Rivest also goes over them. 28169695Skan 29169695Skan The original paper that introduced them is "Fibonacci heaps and their 30169695Skan uses in improved network optimization algorithms" by Tarjan and 31169695Skan Fredman (JACM 34(3), July 1987). 32169695Skan 33169695Skan Amortized and real worst case time for operations: 34169695Skan 35169695Skan ExtractMin: O(lg n) amortized. O(n) worst case. 36169695Skan DecreaseKey: O(1) amortized. O(lg n) worst case. 37169695Skan Insert: O(2) amortized. O(1) actual. 38169695Skan Union: O(1) amortized. O(1) actual. */ 39169695Skan 40169695Skan#ifndef _FIBHEAP_H_ 41169695Skan#define _FIBHEAP_H_ 42169695Skan 43169695Skan#include "ansidecl.h" 44169695Skan 45169695Skantypedef long fibheapkey_t; 46169695Skan 47169695Skantypedef struct fibheap 48169695Skan{ 49169695Skan size_t nodes; 50169695Skan struct fibnode *min; 51169695Skan struct fibnode *root; 52169695Skan} *fibheap_t; 53169695Skan 54169695Skantypedef struct fibnode 55169695Skan{ 56169695Skan struct fibnode *parent; 57169695Skan struct fibnode *child; 58169695Skan struct fibnode *left; 59169695Skan struct fibnode *right; 60169695Skan fibheapkey_t key; 61169695Skan void *data; 62169695Skan#if defined (__GNUC__) && (!defined (SIZEOF_INT) || SIZEOF_INT < 4) 63169695Skan __extension__ unsigned long int degree : 31; 64169695Skan __extension__ unsigned long int mark : 1; 65169695Skan#else 66169695Skan unsigned int degree : 31; 67169695Skan unsigned int mark : 1; 68169695Skan#endif 69169695Skan} *fibnode_t; 70169695Skan 71169695Skanextern fibheap_t fibheap_new (void); 72169695Skanextern fibnode_t fibheap_insert (fibheap_t, fibheapkey_t, void *); 73169695Skanextern int fibheap_empty (fibheap_t); 74169695Skanextern fibheapkey_t fibheap_min_key (fibheap_t); 75169695Skanextern fibheapkey_t fibheap_replace_key (fibheap_t, fibnode_t, 76169695Skan fibheapkey_t); 77169695Skanextern void *fibheap_replace_key_data (fibheap_t, fibnode_t, 78169695Skan fibheapkey_t, void *); 79169695Skanextern void *fibheap_extract_min (fibheap_t); 80169695Skanextern void *fibheap_min (fibheap_t); 81169695Skanextern void *fibheap_replace_data (fibheap_t, fibnode_t, void *); 82169695Skanextern void *fibheap_delete_node (fibheap_t, fibnode_t); 83169695Skanextern void fibheap_delete (fibheap_t); 84169695Skanextern fibheap_t fibheap_union (fibheap_t, fibheap_t); 85169695Skan 86169695Skan#endif /* _FIBHEAP_H_ */ 87