fibheap.h revision 130561
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 1989857Sobrienthe Free Software Foundation, 59 Temple Place - Suite 330, 2089857SobrienBoston, MA 02111-1307, 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; 62130561Sobrien#ifdef __GNUC__ 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 7189857Sobrienextern fibheap_t fibheap_new PARAMS ((void)); 7289857Sobrienextern fibnode_t fibheap_insert PARAMS ((fibheap_t, fibheapkey_t, void *)); 7389857Sobrienextern int fibheap_empty PARAMS ((fibheap_t)); 7489857Sobrienextern fibheapkey_t fibheap_min_key PARAMS ((fibheap_t)); 7589857Sobrienextern fibheapkey_t fibheap_replace_key PARAMS ((fibheap_t, fibnode_t, 7689857Sobrien fibheapkey_t)); 7789857Sobrienextern void *fibheap_replace_key_data PARAMS ((fibheap_t, fibnode_t, 7889857Sobrien fibheapkey_t, void *)); 7989857Sobrienextern void *fibheap_extract_min PARAMS ((fibheap_t)); 8089857Sobrienextern void *fibheap_min PARAMS ((fibheap_t)); 8189857Sobrienextern void *fibheap_replace_data PARAMS ((fibheap_t, fibnode_t, void *)); 8289857Sobrienextern void *fibheap_delete_node PARAMS ((fibheap_t, fibnode_t)); 8389857Sobrienextern void fibheap_delete PARAMS ((fibheap_t)); 8489857Sobrienextern fibheap_t fibheap_union PARAMS ((fibheap_t, fibheap_t)); 8589857Sobrien 8689857Sobrien#endif /* _FIBHEAP_H_ */ 87