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