Back to index

cell-binutils  2.17cvs20070401
fibheap.h
Go to the documentation of this file.
00001 /* A Fibonacci heap datatype.
00002    Copyright 1998, 1999, 2000, 2001, 2002 Free Software Foundation, Inc.
00003    Contributed by Daniel Berlin (dan@cgsoftware.com).
00004 
00005 This file is part of GCC.
00006    
00007 GCC is free software; you can redistribute it and/or modify it
00008 under the terms of the GNU General Public License as published by
00009 the Free Software Foundation; either version 2, or (at your option)
00010 any later version.
00011 
00012 GCC is distributed in the hope that it will be useful, but
00013 WITHOUT ANY WARRANTY; without even the implied warranty of
00014 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
00015 General Public License for more details.
00016 
00017 You should have received a copy of the GNU General Public License
00018 along with GCC; see the file COPYING.  If not, write to
00019 the Free Software Foundation, 51 Franklin Street - Fifth Floor,
00020 Boston, MA 02110-1301, USA.  */
00021 
00022 /* Fibonacci heaps are somewhat complex, but, there's an article in
00023    DDJ that explains them pretty well:
00024 
00025    http://www.ddj.com/articles/1997/9701/9701o/9701o.htm?topic=algoritms
00026 
00027    Introduction to algorithms by Corman and Rivest also goes over them.
00028 
00029    The original paper that introduced them is "Fibonacci heaps and their
00030    uses in improved network optimization algorithms" by Tarjan and
00031    Fredman (JACM 34(3), July 1987).
00032 
00033    Amortized and real worst case time for operations:
00034 
00035    ExtractMin: O(lg n) amortized. O(n) worst case.
00036    DecreaseKey: O(1) amortized.  O(lg n) worst case. 
00037    Insert: O(2) amortized. O(1) actual.  
00038    Union: O(1) amortized. O(1) actual.  */
00039 
00040 #ifndef _FIBHEAP_H_
00041 #define _FIBHEAP_H_
00042 
00043 #include "ansidecl.h"
00044 
00045 typedef long fibheapkey_t;
00046 
00047 typedef struct fibheap
00048 {
00049   size_t nodes;
00050   struct fibnode *min;
00051   struct fibnode *root;
00052 } *fibheap_t;
00053 
00054 typedef struct fibnode
00055 {
00056   struct fibnode *parent;
00057   struct fibnode *child;
00058   struct fibnode *left;
00059   struct fibnode *right;
00060   fibheapkey_t key;
00061   void *data;
00062 #if defined (__GNUC__) && (!defined (SIZEOF_INT) || SIZEOF_INT < 4)
00063   __extension__ unsigned long int degree : 31;
00064   __extension__ unsigned long int mark : 1;
00065 #else
00066   unsigned int degree : 31;
00067   unsigned int mark : 1;
00068 #endif
00069 } *fibnode_t;
00070 
00071 extern fibheap_t fibheap_new (void);
00072 extern fibnode_t fibheap_insert (fibheap_t, fibheapkey_t, void *);
00073 extern int fibheap_empty (fibheap_t);
00074 extern fibheapkey_t fibheap_min_key (fibheap_t);
00075 extern fibheapkey_t fibheap_replace_key (fibheap_t, fibnode_t,
00076                                          fibheapkey_t);
00077 extern void *fibheap_replace_key_data (fibheap_t, fibnode_t,
00078                                        fibheapkey_t, void *);
00079 extern void *fibheap_extract_min (fibheap_t);
00080 extern void *fibheap_min (fibheap_t);
00081 extern void *fibheap_replace_data (fibheap_t, fibnode_t, void *);
00082 extern void *fibheap_delete_node (fibheap_t, fibnode_t);
00083 extern void fibheap_delete (fibheap_t);
00084 extern fibheap_t fibheap_union (fibheap_t, fibheap_t);
00085 
00086 #endif /* _FIBHEAP_H_ */