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-2024 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

◆ ~fibonacci_heap()

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 fibonacci_node< K, V >::m_mark, fibonacci_node< K, V >::m_parent, NULL, and y.

◆ 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

◆ 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, and fibonacci_node< K, V >::m_data.

Referenced by mark_bb_visited(), 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 fibonacci_node< K, V >::m_data, NULL, and fibonacci_node< K, V >::remove().

Referenced by 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 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 fibonacci_node< K, V >::m_key, and NULL.

◆ 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

◆ min_key()

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

◆ nodes()

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

◆ 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, NULL, and fibonacci_node< K, V >::remove().

◆ replace_data()

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

◆ replace_key()

◆ replace_key_data()

template<class K , class V >
V * fibonacci_heap< K, V >::replace_key_data ( fibonacci_node_t * node,
K key,
V * data )

◆ union_with()

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

◆ m_global_min_key

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

◆ 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: