1*a9fa9459Szrj /* A Fibonacci heap datatype. 2*a9fa9459Szrj Copyright (C) 1998-2016 Free Software Foundation, Inc. 3*a9fa9459Szrj Contributed by Daniel Berlin (dan@cgsoftware.com). 4*a9fa9459Szrj 5*a9fa9459Szrj This file is part of GCC. 6*a9fa9459Szrj 7*a9fa9459Szrj GCC is free software; you can redistribute it and/or modify it 8*a9fa9459Szrj under the terms of the GNU General Public License as published by 9*a9fa9459Szrj the Free Software Foundation; either version 2, or (at your option) 10*a9fa9459Szrj any later version. 11*a9fa9459Szrj 12*a9fa9459Szrj GCC is distributed in the hope that it will be useful, but 13*a9fa9459Szrj WITHOUT ANY WARRANTY; without even the implied warranty of 14*a9fa9459Szrj MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 15*a9fa9459Szrj General Public License for more details. 16*a9fa9459Szrj 17*a9fa9459Szrj You should have received a copy of the GNU General Public License 18*a9fa9459Szrj along with GCC; see the file COPYING. If not, write to 19*a9fa9459Szrj the Free Software Foundation, 51 Franklin Street - Fifth Floor, 20*a9fa9459Szrj Boston, MA 02110-1301, USA. */ 21*a9fa9459Szrj 22*a9fa9459Szrj /* Fibonacci heaps are somewhat complex, but, there's an article in 23*a9fa9459Szrj DDJ that explains them pretty well: 24*a9fa9459Szrj 25*a9fa9459Szrj http://www.ddj.com/articles/1997/9701/9701o/9701o.htm?topic=algoritms 26*a9fa9459Szrj 27*a9fa9459Szrj Introduction to algorithms by Corman and Rivest also goes over them. 28*a9fa9459Szrj 29*a9fa9459Szrj The original paper that introduced them is "Fibonacci heaps and their 30*a9fa9459Szrj uses in improved network optimization algorithms" by Tarjan and 31*a9fa9459Szrj Fredman (JACM 34(3), July 1987). 32*a9fa9459Szrj 33*a9fa9459Szrj Amortized and real worst case time for operations: 34*a9fa9459Szrj 35*a9fa9459Szrj ExtractMin: O(lg n) amortized. O(n) worst case. 36*a9fa9459Szrj DecreaseKey: O(1) amortized. O(lg n) worst case. 37*a9fa9459Szrj Insert: O(2) amortized. O(1) actual. 38*a9fa9459Szrj Union: O(1) amortized. O(1) actual. */ 39*a9fa9459Szrj 40*a9fa9459Szrj #ifndef _FIBHEAP_H_ 41*a9fa9459Szrj #define _FIBHEAP_H_ 42*a9fa9459Szrj 43*a9fa9459Szrj #include "ansidecl.h" 44*a9fa9459Szrj 45*a9fa9459Szrj #ifdef __cplusplus 46*a9fa9459Szrj extern "C" { 47*a9fa9459Szrj #endif 48*a9fa9459Szrj 49*a9fa9459Szrj typedef long fibheapkey_t; 50*a9fa9459Szrj 51*a9fa9459Szrj typedef struct fibheap 52*a9fa9459Szrj { 53*a9fa9459Szrj size_t nodes; 54*a9fa9459Szrj struct fibnode *min; 55*a9fa9459Szrj struct fibnode *root; 56*a9fa9459Szrj } *fibheap_t; 57*a9fa9459Szrj 58*a9fa9459Szrj typedef struct fibnode 59*a9fa9459Szrj { 60*a9fa9459Szrj struct fibnode *parent; 61*a9fa9459Szrj struct fibnode *child; 62*a9fa9459Szrj struct fibnode *left; 63*a9fa9459Szrj struct fibnode *right; 64*a9fa9459Szrj fibheapkey_t key; 65*a9fa9459Szrj void *data; 66*a9fa9459Szrj #if defined (__GNUC__) && (!defined (SIZEOF_INT) || SIZEOF_INT < 4) 67*a9fa9459Szrj __extension__ unsigned long int degree : 31; 68*a9fa9459Szrj __extension__ unsigned long int mark : 1; 69*a9fa9459Szrj #else 70*a9fa9459Szrj unsigned int degree : 31; 71*a9fa9459Szrj unsigned int mark : 1; 72*a9fa9459Szrj #endif 73*a9fa9459Szrj } *fibnode_t; 74*a9fa9459Szrj 75*a9fa9459Szrj extern fibheap_t fibheap_new (void); 76*a9fa9459Szrj extern fibnode_t fibheap_insert (fibheap_t, fibheapkey_t, void *); 77*a9fa9459Szrj extern int fibheap_empty (fibheap_t); 78*a9fa9459Szrj extern fibheapkey_t fibheap_min_key (fibheap_t); 79*a9fa9459Szrj extern fibheapkey_t fibheap_replace_key (fibheap_t, fibnode_t, 80*a9fa9459Szrj fibheapkey_t); 81*a9fa9459Szrj extern void *fibheap_replace_key_data (fibheap_t, fibnode_t, 82*a9fa9459Szrj fibheapkey_t, void *); 83*a9fa9459Szrj extern void *fibheap_extract_min (fibheap_t); 84*a9fa9459Szrj extern void *fibheap_min (fibheap_t); 85*a9fa9459Szrj extern void *fibheap_replace_data (fibheap_t, fibnode_t, void *); 86*a9fa9459Szrj extern void *fibheap_delete_node (fibheap_t, fibnode_t); 87*a9fa9459Szrj extern void fibheap_delete (fibheap_t); 88*a9fa9459Szrj extern fibheap_t fibheap_union (fibheap_t, fibheap_t); 89*a9fa9459Szrj 90*a9fa9459Szrj #ifdef __cplusplus 91*a9fa9459Szrj } 92*a9fa9459Szrj #endif 93*a9fa9459Szrj 94*a9fa9459Szrj #endif /* _FIBHEAP_H_ */ 95