189857Sobrien/* A Fibonacci heap datatype. 2104834Sobrien Copyright 1998, 1999, 2000, 2001, 2002 Free Software Foundation, Inc. 389857Sobrien Contributed by Daniel Berlin (dan@cgsoftware.com). 489857Sobrien 589857SobrienThis file is part of GCC. 689857Sobrien 789857SobrienGCC is free software; you can redistribute it and/or modify it 889857Sobrienunder the terms of the GNU General Public License as published by 989857Sobrienthe Free Software Foundation; either version 2, or (at your option) 1089857Sobrienany later version. 1189857Sobrien 1289857SobrienGCC is distributed in the hope that it will be useful, but 1389857SobrienWITHOUT ANY WARRANTY; without even the implied warranty of 1489857SobrienMERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 1589857SobrienGeneral Public License for more details. 1689857Sobrien 1789857SobrienYou should have received a copy of the GNU General Public License 1889857Sobrienalong with GCC; see the file COPYING. If not, write to 19218822Sdimthe Free Software Foundation, 51 Franklin Street - Fifth Floor, 20218822SdimBoston, MA 02110-1301, USA. */ 2189857Sobrien 2289857Sobrien/* Fibonacci heaps are somewhat complex, but, there's an article in 2389857Sobrien DDJ that explains them pretty well: 2489857Sobrien 2589857Sobrien http://www.ddj.com/articles/1997/9701/9701o/9701o.htm?topic=algoritms 2689857Sobrien 2789857Sobrien Introduction to algorithms by Corman and Rivest also goes over them. 2889857Sobrien 2989857Sobrien The original paper that introduced them is "Fibonacci heaps and their 3089857Sobrien uses in improved network optimization algorithms" by Tarjan and 3189857Sobrien Fredman (JACM 34(3), July 1987). 3289857Sobrien 3389857Sobrien Amortized and real worst case time for operations: 3489857Sobrien 3589857Sobrien ExtractMin: O(lg n) amortized. O(n) worst case. 3689857Sobrien DecreaseKey: O(1) amortized. O(lg n) worst case. 3789857Sobrien Insert: O(2) amortized. O(1) actual. 3889857Sobrien Union: O(1) amortized. O(1) actual. */ 3989857Sobrien 4089857Sobrien#ifndef _FIBHEAP_H_ 4189857Sobrien#define _FIBHEAP_H_ 4289857Sobrien 43104834Sobrien#include "ansidecl.h" 4489857Sobrien 4589857Sobrientypedef long fibheapkey_t; 4689857Sobrien 4789857Sobrientypedef struct fibheap 4889857Sobrien{ 4989857Sobrien size_t nodes; 5089857Sobrien struct fibnode *min; 5189857Sobrien struct fibnode *root; 5289857Sobrien} *fibheap_t; 5389857Sobrien 5489857Sobrientypedef struct fibnode 5589857Sobrien{ 5689857Sobrien struct fibnode *parent; 5789857Sobrien struct fibnode *child; 5889857Sobrien struct fibnode *left; 5989857Sobrien struct fibnode *right; 6089857Sobrien fibheapkey_t key; 6189857Sobrien void *data; 62218822Sdim#if defined (__GNUC__) && (!defined (SIZEOF_INT) || SIZEOF_INT < 4) 63130561Sobrien __extension__ unsigned long int degree : 31; 64130561Sobrien __extension__ unsigned long int mark : 1; 65130561Sobrien#else 6689857Sobrien unsigned int degree : 31; 6789857Sobrien unsigned int mark : 1; 68130561Sobrien#endif 6989857Sobrien} *fibnode_t; 7089857Sobrien 71218822Sdimextern fibheap_t fibheap_new (void); 72218822Sdimextern fibnode_t fibheap_insert (fibheap_t, fibheapkey_t, void *); 73218822Sdimextern int fibheap_empty (fibheap_t); 74218822Sdimextern fibheapkey_t fibheap_min_key (fibheap_t); 75218822Sdimextern fibheapkey_t fibheap_replace_key (fibheap_t, fibnode_t, 76218822Sdim fibheapkey_t); 77218822Sdimextern void *fibheap_replace_key_data (fibheap_t, fibnode_t, 78218822Sdim fibheapkey_t, void *); 79218822Sdimextern void *fibheap_extract_min (fibheap_t); 80218822Sdimextern void *fibheap_min (fibheap_t); 81218822Sdimextern void *fibheap_replace_data (fibheap_t, fibnode_t, void *); 82218822Sdimextern void *fibheap_delete_node (fibheap_t, fibnode_t); 83218822Sdimextern void fibheap_delete (fibheap_t); 84218822Sdimextern fibheap_t fibheap_union (fibheap_t, fibheap_t); 8589857Sobrien 8689857Sobrien#endif /* _FIBHEAP_H_ */ 87