fibheap.h revision 89857
189857Sobrien/* A Fibonacci heap datatype. 289857Sobrien Copyright 1998, 1999, 2000, 2001 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 4389857Sobrien#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; 6289857Sobrien unsigned int degree : 31; 6389857Sobrien unsigned int mark : 1; 6489857Sobrien} *fibnode_t; 6589857Sobrien 6689857Sobrienextern fibheap_t fibheap_new PARAMS ((void)); 6789857Sobrienextern fibnode_t fibheap_insert PARAMS ((fibheap_t, fibheapkey_t, void *)); 6889857Sobrienextern int fibheap_empty PARAMS ((fibheap_t)); 6989857Sobrienextern fibheapkey_t fibheap_min_key PARAMS ((fibheap_t)); 7089857Sobrienextern fibheapkey_t fibheap_replace_key PARAMS ((fibheap_t, fibnode_t, 7189857Sobrien fibheapkey_t)); 7289857Sobrienextern void *fibheap_replace_key_data PARAMS ((fibheap_t, fibnode_t, 7389857Sobrien fibheapkey_t, void *)); 7489857Sobrienextern void *fibheap_extract_min PARAMS ((fibheap_t)); 7589857Sobrienextern void *fibheap_min PARAMS ((fibheap_t)); 7689857Sobrienextern void *fibheap_replace_data PARAMS ((fibheap_t, fibnode_t, void *)); 7789857Sobrienextern void *fibheap_delete_node PARAMS ((fibheap_t, fibnode_t)); 7889857Sobrienextern void fibheap_delete PARAMS ((fibheap_t)); 7989857Sobrienextern fibheap_t fibheap_union PARAMS ((fibheap_t, fibheap_t)); 8089857Sobrien 8189857Sobrien#endif /* _FIBHEAP_H_ */ 82