1130803Smarcel/* A Fibonacci heap datatype. 2130803Smarcel Copyright 1998, 1999, 2000, 2001, 2002 Free Software Foundation, Inc. 3130803Smarcel Contributed by Daniel Berlin (dan@cgsoftware.com). 4130803Smarcel 5130803SmarcelThis file is part of GCC. 6130803Smarcel 7130803SmarcelGCC is free software; you can redistribute it and/or modify it 8130803Smarcelunder the terms of the GNU General Public License as published by 9130803Smarcelthe Free Software Foundation; either version 2, or (at your option) 10130803Smarcelany later version. 11130803Smarcel 12130803SmarcelGCC is distributed in the hope that it will be useful, but 13130803SmarcelWITHOUT ANY WARRANTY; without even the implied warranty of 14130803SmarcelMERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 15130803SmarcelGeneral Public License for more details. 16130803Smarcel 17130803SmarcelYou should have received a copy of the GNU General Public License 18130803Smarcelalong with GCC; see the file COPYING. If not, write to 19130803Smarcelthe Free Software Foundation, 59 Temple Place - Suite 330, 20130803SmarcelBoston, MA 02111-1307, USA. */ 21130803Smarcel 22130803Smarcel/* Fibonacci heaps are somewhat complex, but, there's an article in 23130803Smarcel DDJ that explains them pretty well: 24130803Smarcel 25130803Smarcel http://www.ddj.com/articles/1997/9701/9701o/9701o.htm?topic=algoritms 26130803Smarcel 27130803Smarcel Introduction to algorithms by Corman and Rivest also goes over them. 28130803Smarcel 29130803Smarcel The original paper that introduced them is "Fibonacci heaps and their 30130803Smarcel uses in improved network optimization algorithms" by Tarjan and 31130803Smarcel Fredman (JACM 34(3), July 1987). 32130803Smarcel 33130803Smarcel Amortized and real worst case time for operations: 34130803Smarcel 35130803Smarcel ExtractMin: O(lg n) amortized. O(n) worst case. 36130803Smarcel DecreaseKey: O(1) amortized. O(lg n) worst case. 37130803Smarcel Insert: O(2) amortized. O(1) actual. 38130803Smarcel Union: O(1) amortized. O(1) actual. */ 39130803Smarcel 40130803Smarcel#ifndef _FIBHEAP_H_ 41130803Smarcel#define _FIBHEAP_H_ 42130803Smarcel 43130803Smarcel#include "ansidecl.h" 44130803Smarcel 45130803Smarceltypedef long fibheapkey_t; 46130803Smarcel 47130803Smarceltypedef struct fibheap 48130803Smarcel{ 49130803Smarcel size_t nodes; 50130803Smarcel struct fibnode *min; 51130803Smarcel struct fibnode *root; 52130803Smarcel} *fibheap_t; 53130803Smarcel 54130803Smarceltypedef struct fibnode 55130803Smarcel{ 56130803Smarcel struct fibnode *parent; 57130803Smarcel struct fibnode *child; 58130803Smarcel struct fibnode *left; 59130803Smarcel struct fibnode *right; 60130803Smarcel fibheapkey_t key; 61130803Smarcel void *data; 62130803Smarcel#ifdef __GNUC__ 63130803Smarcel __extension__ unsigned long int degree : 31; 64130803Smarcel __extension__ unsigned long int mark : 1; 65130803Smarcel#else 66130803Smarcel unsigned int degree : 31; 67130803Smarcel unsigned int mark : 1; 68130803Smarcel#endif 69130803Smarcel} *fibnode_t; 70130803Smarcel 71130803Smarcelextern fibheap_t fibheap_new PARAMS ((void)); 72130803Smarcelextern fibnode_t fibheap_insert PARAMS ((fibheap_t, fibheapkey_t, void *)); 73130803Smarcelextern int fibheap_empty PARAMS ((fibheap_t)); 74130803Smarcelextern fibheapkey_t fibheap_min_key PARAMS ((fibheap_t)); 75130803Smarcelextern fibheapkey_t fibheap_replace_key PARAMS ((fibheap_t, fibnode_t, 76130803Smarcel fibheapkey_t)); 77130803Smarcelextern void *fibheap_replace_key_data PARAMS ((fibheap_t, fibnode_t, 78130803Smarcel fibheapkey_t, void *)); 79130803Smarcelextern void *fibheap_extract_min PARAMS ((fibheap_t)); 80130803Smarcelextern void *fibheap_min PARAMS ((fibheap_t)); 81130803Smarcelextern void *fibheap_replace_data PARAMS ((fibheap_t, fibnode_t, void *)); 82130803Smarcelextern void *fibheap_delete_node PARAMS ((fibheap_t, fibnode_t)); 83130803Smarcelextern void fibheap_delete PARAMS ((fibheap_t)); 84130803Smarcelextern fibheap_t fibheap_union PARAMS ((fibheap_t, fibheap_t)); 85130803Smarcel 86130803Smarcel#endif /* _FIBHEAP_H_ */ 87