GCC Middle and Back End API Reference
fibonacci_heap< K, V > Class Template Reference

#include <fibonacci_heap.h>

Inheritance diagram for fibonacci_heap< K, V >:
Collaboration diagram for fibonacci_heap< K, V >:

Public Member Functions

 fibonacci_heap (K global_min_key, pool_allocator *allocator=NULL)
 
 ~fibonacci_heap ()
 
fibonacci_node_tinsert (K key, V *data)
 
bool empty () const
 
size_t nodes () const
 
min_key () const
 
replace_key (fibonacci_node_t *node, K key)
 
decrease_key (fibonacci_node_t *node, K key)
 
V * replace_key_data (fibonacci_node_t *node, K key, V *data)
 
V * extract_min (bool release=true)
 
V * min () const
 
V * replace_data (fibonacci_node_t *node, V *data)
 
V * delete_node (fibonacci_node_t *node, bool release=true)
 
fibonacci_heapunion_with (fibonacci_heap *heapb)
 

Private Types

typedef fibonacci_node< K, V > fibonacci_node_t
 

Private Member Functions

fibonacci_node_tinsert (fibonacci_node_t *node, K key, V *data)
 
fibonacci_node_tinsert_node (fibonacci_node_t *node)
 
void insert_root (fibonacci_node_t *node)
 
void cut (fibonacci_node_t *node, fibonacci_node_t *parent)
 
void cascading_cut (fibonacci_node_t *y)
 
fibonacci_node_textract_minimum_node ()
 
void remove_root (fibonacci_node_t *node)
 
void consolidate ()
 

Private Attributes

size_t m_nodes
 
fibonacci_node_tm_min
 
fibonacci_node_tm_root
 
m_global_min_key
 
pool_allocatorm_allocator
 
bool m_own_allocator
 

Friends

class fibonacci_node< K, V >
 

Detailed Description

template<class K, class V>
class fibonacci_heap< K, V >
Fibonacci heap for GNU compiler. Copyright (C) 1998-2025 Free Software Foundation, Inc. Contributed by Daniel Berlin (dan@cgsoftware.com). Re-implemented in C++ by Martin Liska <mliska@suse.cz> This file is part of GCC. GCC is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 3, or (at your option) any later version. GCC is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with GCC; see the file COPYING3. If not see <http://www.gnu.org/licenses/>.
Fibonacci heaps are somewhat complex, but, there's an article in DDJ that explains them pretty well: http://www.ddj.com/articles/1997/9701/9701o/9701o.htm?topic=algoritms Introduction to algorithms by Corman and Rivest also goes over them. The original paper that introduced them is "Fibonacci heaps and their uses in improved network optimization algorithms" by Tarjan and Fredman (JACM 34(3), July 1987). Amortized and real worst case time for operations: ExtractMin: O(lg n) amortized. O(n) worst case. DecreaseKey: O(1) amortized. O(lg n) worst case. Insert: O(1) amortized. Union: O(1) amortized.
Forward definition.
Fibonacci heap class.

Member Typedef Documentation

◆ fibonacci_node_t

template<class K, class V>
typedef fibonacci_node<K,V> fibonacci_heap< K, V >::fibonacci_node_t
private

Constructor & Destructor Documentation

◆ fibonacci_heap()

template<class K, class V>
fibonacci_heap< K, V >::fibonacci_heap ( K global_min_key,
pool_allocator * allocator = NULL )
inline

Referenced by union_with().

◆ ~fibonacci_heap()

template<class K, class V>
fibonacci_heap< K, V >::~fibonacci_heap ( )
inline

Member Function Documentation

◆ cascading_cut()

template<class K, class V>
void fibonacci_heap< K, V >::cascading_cut ( fibonacci_node_t * y)
private
Process cut of node Y and do it recursivelly.

References cut(), NULL, and y.

Referenced by replace_key_data().

◆ consolidate()

template<class K, class V>
void fibonacci_heap< K, V >::consolidate ( )
private

◆ cut()

template<class K, class V>
void fibonacci_heap< K, V >::cut ( fibonacci_node_t * node,
fibonacci_node_t * parent )
private

◆ decrease_key()

template<class K, class V>
K fibonacci_heap< K, V >::decrease_key ( fibonacci_node_t * node,
K key )
inline

Referenced by update_edge_key().

◆ delete_node()

template<class K, class V>
V * fibonacci_heap< K, V >::delete_node ( fibonacci_node_t * node,
bool release = true )
Delete NODE in the heap, if RELEASE is specified memory is released.

References abort, extract_min(), fibonacci_node< K, V >::m_data, m_global_min_key, m_min, and replace_key().

Referenced by replace_key_data(), tail_duplicate(), update_callee_keys(), and update_caller_keys().

◆ empty()

template<class K, class V>
bool fibonacci_heap< K, V >::empty ( ) const
inline

◆ extract_min()

template<class K, class V>
V * fibonacci_heap< K, V >::extract_min ( bool release = true)
Extract minimum node in the heap. Delete fibonacci node if RELEASE is true.

References extract_minimum_node(), m_allocator, fibonacci_node< K, V >::m_data, m_min, and NULL.

Referenced by delete_node(), inline_small_functions(), recursive_inlining(), and tail_duplicate().

◆ extract_minimum_node()

template<class K, class V>
fibonacci_node< K, V > * fibonacci_heap< K, V >::extract_minimum_node ( )
private

◆ insert() [1/2]

template<class K, class V>
fibonacci_node< K, V > * fibonacci_heap< K, V >::insert ( fibonacci_node_t * node,
K key,
V * data )
private
Insert new NODE given by DATA associated with the key.

References insert_node(), fibonacci_node< K, V >::m_data, and fibonacci_node< K, V >::m_key.

◆ insert() [2/2]

template<class K, class V>
fibonacci_node< K, V > * fibonacci_heap< K, V >::insert ( K key,
V * data )

◆ insert_node()

template<class K, class V>
fibonacci_node< K, V > * fibonacci_heap< K, V >::insert_node ( fibonacci_node_t * node)
private
Insert new NODE that has already filled key and value.

References insert_root(), fibonacci_node< K, V >::m_key, m_min, m_nodes, and NULL.

Referenced by insert(), and insert().

◆ insert_root()

template<class K, class V>
void fibonacci_heap< K, V >::insert_root ( fibonacci_node_t * node)
private

◆ min()

template<class K, class V>
V * fibonacci_heap< K, V >::min ( ) const
inline

Referenced by inline_small_functions().

◆ min_key()

template<class K, class V>
K fibonacci_heap< K, V >::min_key ( ) const
inline

Referenced by inline_small_functions().

◆ nodes()

template<class K, class V>
size_t fibonacci_heap< K, V >::nodes ( ) const
inline

Referenced by vt_find_locations().

◆ remove_root()

template<class K, class V>
void fibonacci_heap< K, V >::remove_root ( fibonacci_node_t * node)
private
Remove root NODE from the heap.

References fibonacci_node< K, V >::m_left, m_root, NULL, and fibonacci_node< K, V >::remove().

Referenced by consolidate(), and extract_minimum_node().

◆ replace_data()

template<class K, class V>
V * fibonacci_heap< K, V >::replace_data ( fibonacci_node_t * node,
V * data )
inline

◆ replace_key()

template<class K, class V>
K fibonacci_heap< K, V >::replace_key ( fibonacci_node_t * node,
K key )
inline

◆ replace_key_data()

◆ union_with()

template<class K, class V>
fibonacci_heap< K, V > * fibonacci_heap< K, V >::union_with ( fibonacci_heap< K, V > * heapb)

Friends And Related Symbol Documentation

◆ fibonacci_node< K, V >

template<class K, class V>
friend class fibonacci_node< K, V >
friend

Field Documentation

◆ m_allocator

template<class K, class V>
pool_allocator* fibonacci_heap< K, V >::m_allocator
private

Referenced by extract_min(), insert(), and union_with().

◆ m_global_min_key

template<class K, class V>
K fibonacci_heap< K, V >::m_global_min_key
private

Referenced by delete_node(), and replace_key_data().

◆ m_min

◆ m_nodes

template<class K, class V>
size_t fibonacci_heap< K, V >::m_nodes
private

◆ m_own_allocator

template<class K, class V>
bool fibonacci_heap< K, V >::m_own_allocator
private

◆ m_root

template<class K, class V>
fibonacci_node_t* fibonacci_heap< K, V >::m_root
private

The documentation for this class was generated from the following file: