Implementation of a Fibonacci Heap priority queue. More...

#include <tpl_fibonacci_heap.H>

Inheritance diagram for Aleph::Fibonacci_Heap< T, Compare >:

Collaboration diagram for Aleph::Fibonacci_Heap< T, Compare >:

Classes
struct	Node
	Represents a node in the Fibonacci Heap. More...

Public Types
using	value_type = T
	Type alias for the element type.

using	key_compare = Compare
	Type alias for the comparison functor.

using	handle_type = Node *
	Type alias for node handles.

Public Member Functions
	Fibonacci_Heap (Compare compare=Compare()) noexcept
	Default constructor.

template<typename... Args>
	Fibonacci_Heap (std::in_place_t, Args &&... args) noexcept
	Constructor with in-place comparator construction.

	~Fibonacci_Heap ()
	Destructor.

	Fibonacci_Heap (const Fibonacci_Heap &)=delete
	Copy constructor is disabled (use merge or manual copy)

Fibonacci_Heap &	operator= (const Fibonacci_Heap &)=delete
	Copy assignment is disabled (use merge or manual copy)

	Fibonacci_Heap (Fibonacci_Heap &&other) noexcept
	Move constructor.

Fibonacci_Heap &	operator= (Fibonacci_Heap &&other) noexcept
	Move assignment operator.

void	swap (Fibonacci_Heap &other) noexcept
	Swaps contents with another heap.

Node *	insert (const T &val)
	Inserts a new element (copy).

Node *	insert (T &&val)
	Inserts a new element (move).

template<typename... Args>
Node *	emplace (Args &&... args)
	Constructs and inserts an element in-place.

const T &	get_min () const
	Returns the minimum element without removing it.

Node *	get_min_node () const noexcept
	Returns a pointer to the minimum node.

T	extract_min ()
	Extracts and returns the minimum element.

void	decrease_key (Node *x, const T &k)
	Decreases the key of a node.

void	decrease_key (Node *x, T &&k)
	Decreases the key of a node (move version).

Node *	update_key (Node *x, const T &k)
	Updates the key of a node (increase or decrease).

void	delete_node (Node *x)
	Deletes a specific node from the heap.

void	merge (Fibonacci_Heap &other)
	Merges another heap into this one.

void	merge (Fibonacci_Heap &&other)
	Merges another heap into this one (rvalue version).

bool	is_empty () const noexcept
	Checks if the heap is empty.

size_t	size () const noexcept
	Returns the number of elements in the heap.

void	clear () noexcept(std::is_nothrow_destructible_v< T >)
	Removes all elements from the heap.

bool	empty () const noexcept

void	pop ()

const T &	top () const

Compare	key_comp () const
	Returns the comparison functor.

Private Member Functions
void	consolidate ()
	Consolidates the root list after extract_min.

void	cut (Node x, Node y)
	Cuts a node from its parent and adds it to the root list.

void	cascading_cut (Node *y)
	Performs cascading cut operation.

void	delete_all_nodes (Node *node)
	Recursively deletes all nodes in a tree.

void	add_to_root_list (Node *node)
	Adds a node to the root list.

Static Private Member Functions
static void	link (Node y, Node x)
	Links two trees of the same degree.

Private Attributes
Node *	min_node = nullptr
	Pointer to the current minimum root.

size_t	num_nodes = 0
	Number of elements stored in the heap.

Compare	cmp
	Comparison functor used to order nodes.

std::vector< Node * >	consolidate_array_
	Reusable scratch array for Fibonacci_Heap::consolidate().

Static Private Attributes
static constexpr size_t	MAX_DEGREE = 128
	Maximum degree tracked during consolidation.

Related Symbols
(Note that these are not member symbols.)
template<typename T , class Compare >
void	swap (Fibonacci_Heap< T, Compare > &a, Fibonacci_Heap< T, Compare > &b) noexcept
	Swaps two Fibonacci heaps.

Detailed Description

template<typename T, class Compare = Aleph::less<T>>
class Aleph::Fibonacci_Heap< T, Compare >

Implementation of a Fibonacci Heap priority queue.

A Fibonacci Heap is a collection of heap-ordered trees that supports a rich set of operations with excellent amortized time complexity. It is particularly well-suited for graph algorithms like Dijkstra's shortest path and Prim's minimum spanning tree where decrease-key operations are frequent.

Time Complexities (Amortized)

Operation	Time Complexity
insert	O(1)
get_min	O(1)
extract_min	O(log n)
decrease_key	O(1)
delete_node	O(log n)
merge	O(1)
is_empty	O(1)
size	O(1)

Usage Example

Fibonacci_Heap<int> heap;
auto n1 = heap.insert(10);
auto n2 = heap.insert(5);
auto n3 = heap.insert(15);
 
std::cout << heap.get_min(); // Outputs: 5
 
heap.decrease_key(n3, 3);    // Decrease 15 to 3
std::cout << heap.get_min(); // Outputs: 3
 
int min = heap.extract_min(); // Returns 3, removes it

Implementation Notes

The heap maintains a circular doubly-linked list of root trees.
Each node can have multiple children organized as a circular list.
The "mark" field tracks whether a node has lost a child since becoming a non-root node (used for cascading cuts).
Copy operations are disabled; use move semantics or merge instead.

Template Parameters

T	The data type of elements stored in the heap.
Compare	The comparison functor (defaults to Aleph::less<T> for a min-heap). Use Aleph::greater<T> for a max-heap.

See also: BinHeap DynBinHeap

Definition at line 111 of file tpl_fibonacci_heap.H.

Member Typedef Documentation

◆ handle_type

template<typename T , class Compare = Aleph::less<T>>

using Aleph::Fibonacci_Heap< T, Compare >::handle_type = Node *

Type alias for node handles.

Definition at line 410 of file tpl_fibonacci_heap.H.

◆ key_compare

template<typename T , class Compare = Aleph::less<T>>

using Aleph::Fibonacci_Heap< T, Compare >::key_compare = Compare

Type alias for the comparison functor.

Definition at line 407 of file tpl_fibonacci_heap.H.

◆ value_type

template<typename T , class Compare = Aleph::less<T>>

using Aleph::Fibonacci_Heap< T, Compare >::value_type = T

Type alias for the element type.

Definition at line 404 of file tpl_fibonacci_heap.H.

Constructor & Destructor Documentation

◆ Fibonacci_Heap() [1/4]

template<typename T , class Compare = Aleph::less<T>>

Aleph::Fibonacci_Heap< T, Compare >::Fibonacci_Heap ( Compare compare = Compare() )

inlineexplicitnoexcept

Default constructor.

Creates an empty heap using a copy of compare to order keys.

Parameters

compare Comparison functor (defaults to Compare()).

Definition at line 419 of file tpl_fibonacci_heap.H.

References Aleph::Fibonacci_Heap< T, Compare >::consolidate_array_, and Aleph::Fibonacci_Heap< T, Compare >::MAX_DEGREE.

◆ Fibonacci_Heap() [2/4]

template<typename T , class Compare = Aleph::less<T>>

template<typename... Args>

Aleph::Fibonacci_Heap< T, Compare >::Fibonacci_Heap	(	std::in_place_t	,
		Args &&...	args
	)

inlineexplicitnoexcept

Constructor with in-place comparator construction.

Allows constructing the comparator from arbitrary arguments. Use std::in_place as first argument to disambiguate.

Template Parameters

Args	Types of comparator constructor arguments

Parameters

args	Arguments forwarded to Compare's constructor

Definition at line 435 of file tpl_fibonacci_heap.H.

References Aleph::Fibonacci_Heap< T, Compare >::consolidate_array_, and Aleph::Fibonacci_Heap< T, Compare >::MAX_DEGREE.

◆ ~Fibonacci_Heap()

template<typename T , class Compare = Aleph::less<T>>

Aleph::Fibonacci_Heap< T, Compare >::~Fibonacci_Heap ( )

inline

Destructor.

Deallocates all nodes. Runs in O(n) time.

Definition at line 446 of file tpl_fibonacci_heap.H.

References Aleph::Fibonacci_Heap< T, Compare >::clear().

◆ Fibonacci_Heap() [3/4]

template<typename T , class Compare = Aleph::less<T>>

Aleph::Fibonacci_Heap< T, Compare >::Fibonacci_Heap ( const Fibonacci_Heap< T, Compare > & )

delete

Copy constructor is disabled (use merge or manual copy)

◆ Fibonacci_Heap() [4/4]

template<typename T , class Compare = Aleph::less<T>>

Aleph::Fibonacci_Heap< T, Compare >::Fibonacci_Heap ( Fibonacci_Heap< T, Compare > && other )

inlinenoexcept

Move constructor.

Transfers ownership of all nodes from other to this heap. The source heap becomes empty.

Parameters

other The heap to move from

Definition at line 465 of file tpl_fibonacci_heap.H.

References Aleph::maps().

Member Function Documentation

◆ add_to_root_list()

template<typename T , class Compare = Aleph::less<T>>

void Aleph::Fibonacci_Heap< T, Compare >::add_to_root_list ( Node * node )

inlineprivate

Adds a node to the root list.

Parameters

node	The node to add (must not be in any list)

Definition at line 381 of file tpl_fibonacci_heap.H.

References Aleph::Fibonacci_Heap< T, Compare >::cmp, Aleph::Fibonacci_Heap< T, Compare >::Node::data, Aleph::Fibonacci_Heap< T, Compare >::Node::left, Aleph::Fibonacci_Heap< T, Compare >::min_node, Aleph::Fibonacci_Heap< T, Compare >::Node::parent, and Aleph::Fibonacci_Heap< T, Compare >::Node::right.

Referenced by Aleph::Fibonacci_Heap< T, Compare >::emplace(), Aleph::Fibonacci_Heap< T, Compare >::insert(), and Aleph::Fibonacci_Heap< T, Compare >::insert().

◆ cascading_cut()

template<typename T , class Compare = Aleph::less<T>>

void Aleph::Fibonacci_Heap< T, Compare >::cascading_cut ( Node * y )

inlineprivate

Performs cascading cut operation.

If y has lost a child before (mark == true), cut it from its parent and recursively check the parent. This maintains the amortized O(1) decrease_key complexity.

Parameters

y	The node to potentially cut

Definition at line 330 of file tpl_fibonacci_heap.H.

References Aleph::Fibonacci_Heap< T, Compare >::cut(), Aleph::maps(), and y.

Referenced by Aleph::Fibonacci_Heap< T, Compare >::decrease_key(), Aleph::Fibonacci_Heap< T, Compare >::decrease_key(), and Aleph::Fibonacci_Heap< T, Compare >::delete_node().

◆ clear()

template<typename T , class Compare = Aleph::less<T>>

void Aleph::Fibonacci_Heap< T, Compare >::clear ( )

inlinenoexcept

Removes all elements from the heap.

Deallocates all nodes and resets the heap to empty state.

Note: O(n) time complexity

Definition at line 924 of file tpl_fibonacci_heap.H.

References Aleph::Fibonacci_Heap< T, Compare >::delete_all_nodes(), Aleph::Fibonacci_Heap< T, Compare >::min_node, and Aleph::Fibonacci_Heap< T, Compare >::num_nodes.

Referenced by Aleph::Fibonacci_Heap< T, Compare >::~Fibonacci_Heap(), ArcFibonacciHeap< GT, Distance, Access_Heap_Node >::empty(), Aleph::Fibonacci_Heap< T, Compare >::operator=(), and TEST().

◆ consolidate()

template<typename T , class Compare = Aleph::less<T>>

void Aleph::Fibonacci_Heap< T, Compare >::consolidate ( )

inlineprivate

Consolidates the root list after extract_min.

Ensures no two roots have the same degree by linking trees of equal degree until all roots have distinct degrees.

Definition at line 222 of file tpl_fibonacci_heap.H.

Referenced by Aleph::Fibonacci_Heap< T, Compare >::delete_node(), and Aleph::Fibonacci_Heap< T, Compare >::extract_min().

◆ cut()

template<typename T , class Compare = Aleph::less<T>>

void Aleph::Fibonacci_Heap< T, Compare >::cut	(	Node *	x,
		Node *	y
	)

inlineprivate

Cuts a node from its parent and adds it to the root list.

Parameters

x	The node to cut
y	The parent of x

Definition at line 298 of file tpl_fibonacci_heap.H.

References Aleph::Fibonacci_Heap< T, Compare >::Node::child, Aleph::Fibonacci_Heap< T, Compare >::Node::degree, Aleph::Fibonacci_Heap< T, Compare >::Node::left, Aleph::Fibonacci_Heap< T, Compare >::Node::mark, Aleph::Fibonacci_Heap< T, Compare >::min_node, Aleph::Fibonacci_Heap< T, Compare >::Node::parent, Aleph::Fibonacci_Heap< T, Compare >::Node::right, and y.

Referenced by Aleph::Fibonacci_Heap< T, Compare >::cascading_cut(), Aleph::Fibonacci_Heap< T, Compare >::decrease_key(), Aleph::Fibonacci_Heap< T, Compare >::decrease_key(), and Aleph::Fibonacci_Heap< T, Compare >::delete_node().

◆ decrease_key() [1/2]

template<typename T , class Compare = Aleph::less<T>>

void Aleph::Fibonacci_Heap< T, Compare >::decrease_key	(	Node *	x,
		const T &	k
	)

inline

Decreases the key of a node.

Decreases the key of node x to the new value k. If this violates the heap property with x's parent, x is cut and added to the root list, potentially triggering cascading cuts.

Parameters

x	Handle to the node (returned by insert/emplace)
k	The new key value (must be <= current key)

Exceptions

std::invalid_argument	if x is nullptr
std::domain_error	if k > current key

Note: Amortized O(1) time complexity

Definition at line 675 of file tpl_fibonacci_heap.H.

References ah_domain_error_if, ah_invalid_argument_if, Aleph::Fibonacci_Heap< T, Compare >::cascading_cut(), Aleph::Fibonacci_Heap< T, Compare >::cmp, Aleph::Fibonacci_Heap< T, Compare >::cut(), Aleph::Fibonacci_Heap< T, Compare >::Node::data, Aleph::maps(), Aleph::Fibonacci_Heap< T, Compare >::min_node, Aleph::Fibonacci_Heap< T, Compare >::Node::parent, and y.

Referenced by demo_performance_comparison(), ArcFibonacciHeap< GT, Distance, Access_Heap_Node >::put_arc(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), and Aleph::Fibonacci_Heap< T, Compare >::update_key().

◆ decrease_key() [2/2]

template<typename T , class Compare = Aleph::less<T>>

void Aleph::Fibonacci_Heap< T, Compare >::decrease_key	(	Node *	x,
		T &&	k
	)

inline

Decreases the key of a node (move version).

Parameters

x	Handle to the node
k	The new key value (moved into node)

Definition at line 701 of file tpl_fibonacci_heap.H.

References ah_domain_error_if, ah_invalid_argument_if, Aleph::Fibonacci_Heap< T, Compare >::cascading_cut(), Aleph::Fibonacci_Heap< T, Compare >::cmp, Aleph::Fibonacci_Heap< T, Compare >::cut(), Aleph::Fibonacci_Heap< T, Compare >::Node::data, Aleph::maps(), Aleph::Fibonacci_Heap< T, Compare >::min_node, Aleph::Fibonacci_Heap< T, Compare >::Node::parent, and y.

◆ delete_all_nodes()

template<typename T , class Compare = Aleph::less<T>>

void Aleph::Fibonacci_Heap< T, Compare >::delete_all_nodes ( Node * node )

inlineprivate

Recursively deletes all nodes in a tree.

Used by clear() for O(n) cleanup instead of O(n log n).

Parameters

node	Root of the subtree to delete

Definition at line 355 of file tpl_fibonacci_heap.H.

References Aleph::Fibonacci_Heap< T, Compare >::Node::child, Aleph::Fibonacci_Heap< T, Compare >::delete_all_nodes(), Aleph::Fibonacci_Heap< T, Compare >::Node::left, Aleph::next(), and Aleph::Fibonacci_Heap< T, Compare >::Node::right.

Referenced by Aleph::Fibonacci_Heap< T, Compare >::clear(), and Aleph::Fibonacci_Heap< T, Compare >::delete_all_nodes().

◆ delete_node()

template<typename T , class Compare = Aleph::less<T>>

void Aleph::Fibonacci_Heap< T, Compare >::delete_node ( Node * x )

inline

Deletes a specific node from the heap.

Removes the node x from the heap regardless of its position.

Parameters

x	Handle to the node to delete

Exceptions

std::invalid_argument if x is nullptr

Note: Amortized O(log n) time complexity

Warning: After this call, x is invalid and must not be used.

Definition at line 767 of file tpl_fibonacci_heap.H.

References ah_invalid_argument_if, Aleph::Fibonacci_Heap< T, Compare >::cascading_cut(), Aleph::Fibonacci_Heap< T, Compare >::Node::child, Aleph::Fibonacci_Heap< T, Compare >::consolidate(), Aleph::Fibonacci_Heap< T, Compare >::cut(), Aleph::Fibonacci_Heap< T, Compare >::Node::left, Aleph::maps(), Aleph::Fibonacci_Heap< T, Compare >::min_node, Aleph::Fibonacci_Heap< T, Compare >::num_nodes, Aleph::Fibonacci_Heap< T, Compare >::Node::parent, and Aleph::Fibonacci_Heap< T, Compare >::Node::right.

Referenced by TEST(), TEST(), TEST(), TEST(), TEST(), and Aleph::Fibonacci_Heap< T, Compare >::update_key().

◆ emplace()

template<typename T , class Compare = Aleph::less<T>>

template<typename... Args>

Node * Aleph::Fibonacci_Heap< T, Compare >::emplace ( Args &&... args )

inline

Constructs and inserts an element in-place.

Constructs the element directly in the node using the provided arguments, avoiding unnecessary copies or moves.

Template Parameters

Args	Types of constructor arguments

Parameters

args	Arguments to forward to T's constructor

Returns: A handle to the created node

Note: Amortized O(1) time complexity

Definition at line 564 of file tpl_fibonacci_heap.H.

References Aleph::Fibonacci_Heap< T, Compare >::add_to_root_list(), Aleph::maps(), and Aleph::Fibonacci_Heap< T, Compare >::num_nodes.

Referenced by TEST().

◆ empty()

template<typename T , class Compare = Aleph::less<T>>

bool Aleph::Fibonacci_Heap< T, Compare >::empty ( ) const

inlinenoexcept

Definition at line 934 of file tpl_fibonacci_heap.H.

References Aleph::Fibonacci_Heap< T, Compare >::is_empty().

◆ extract_min()

template<typename T , class Compare = Aleph::less<T>>

T Aleph::Fibonacci_Heap< T, Compare >::extract_min ( )

inline

Extracts and returns the minimum element.

Removes the minimum element from the heap and returns it. The heap is restructured (consolidated) after removal.

Returns: The minimum element (moved out)

Exceptions

std::underflow_error if the heap is empty

Note: Amortized O(log n) time complexity

Definition at line 611 of file tpl_fibonacci_heap.H.

References ah_underflow_error_if, Aleph::Fibonacci_Heap< T, Compare >::consolidate(), Aleph::Fibonacci_Heap< T, Compare >::is_empty(), Aleph::maps(), Aleph::Fibonacci_Heap< T, Compare >::min_node, Aleph::Fibonacci_Heap< T, Compare >::num_nodes, Aleph::Fibonacci_Heap< T, Compare >::Node::parent, and Aleph::Fibonacci_Heap< T, Compare >::Node::right.

Referenced by demo_performance_comparison(), ArcFibonacciHeap< GT, Distance, Access_Heap_Node >::get_min_arc(), Aleph::Fibonacci_Heap< T, Compare >::pop(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), and verify_heap_property().

◆ get_min()

template<typename T , class Compare = Aleph::less<T>>

const T & Aleph::Fibonacci_Heap< T, Compare >::get_min ( ) const

inline

Returns the minimum element without removing it.

Returns: Const reference to the minimum element

Exceptions

std::underflow_error if the heap is empty

Note: O(1) time complexity

Definition at line 580 of file tpl_fibonacci_heap.H.

References ah_underflow_error_if, Aleph::Fibonacci_Heap< T, Compare >::Node::data, Aleph::Fibonacci_Heap< T, Compare >::is_empty(), and Aleph::Fibonacci_Heap< T, Compare >::min_node.

Referenced by TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), and Aleph::Fibonacci_Heap< T, Compare >::top().

◆ get_min_node()

template<typename T , class Compare = Aleph::less<T>>

Node * Aleph::Fibonacci_Heap< T, Compare >::get_min_node ( ) const

inlinenoexcept

Returns a pointer to the minimum node.

Useful when you need the handle rather than just the value.

Returns: Pointer to the minimum node, or nullptr if empty

Note: O(1) time complexity

Definition at line 595 of file tpl_fibonacci_heap.H.

References Aleph::Fibonacci_Heap< T, Compare >::min_node.

Referenced by ArcFibonacciHeap< GT, Distance, Access_Heap_Node >::get_min_arc(), and TEST().

◆ insert() [1/2]

template<typename T , class Compare = Aleph::less<T>>

Node * Aleph::Fibonacci_Heap< T, Compare >::insert ( const T & val )

inline

Inserts a new element (copy).

Creates a new node with a copy of val and adds it to the heap.

Parameters

val	The value to insert

Returns: A handle (pointer) to the created node for later operations

Note: Amortized O(1) time complexity; The return value can be safely ignored if you don't need the handle for decrease_key or delete_node operations.

Definition at line 525 of file tpl_fibonacci_heap.H.

References Aleph::Fibonacci_Heap< T, Compare >::add_to_root_list(), and Aleph::Fibonacci_Heap< T, Compare >::num_nodes.

Referenced by demo_performance_comparison(), ArcFibonacciHeap< GT, Distance, Access_Heap_Node >::put_arc(), FibonacciHeapWithDataTest::SetUp(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), and Aleph::Fibonacci_Heap< T, Compare >::update_key().

◆ insert() [2/2]

template<typename T , class Compare = Aleph::less<T>>

Node * Aleph::Fibonacci_Heap< T, Compare >::insert ( T && val )

inline

Inserts a new element (move).

Creates a new node by moving val into it.

Parameters

val	The value to insert (will be moved)

Returns: A handle to the created node

Note: Amortized O(1) time complexity

Definition at line 543 of file tpl_fibonacci_heap.H.

References Aleph::Fibonacci_Heap< T, Compare >::add_to_root_list(), and Aleph::Fibonacci_Heap< T, Compare >::num_nodes.

◆ is_empty()

template<typename T , class Compare = Aleph::less<T>>

bool Aleph::Fibonacci_Heap< T, Compare >::is_empty ( ) const

inlinenoexcept

Checks if the heap is empty.

Returns: true if the heap has no elements, false otherwise

Note: O(1) time complexity

Definition at line 900 of file tpl_fibonacci_heap.H.

References Aleph::Fibonacci_Heap< T, Compare >::min_node.

Referenced by demo_performance_comparison(), Aleph::Fibonacci_Heap< T, Compare >::empty(), Aleph::Fibonacci_Heap< T, Compare >::extract_min(), Aleph::Fibonacci_Heap< T, Compare >::get_min(), ArcFibonacciHeap< GT, Distance, Access_Heap_Node >::get_min_arc(), ArcFibonacciHeap< GT, Distance, Access_Heap_Node >::is_empty(), Aleph::Fibonacci_Heap< T, Compare >::merge(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), and verify_heap_property().

◆ key_comp()

template<typename T , class Compare = Aleph::less<T>>

Compare Aleph::Fibonacci_Heap< T, Compare >::key_comp ( ) const

inline

Returns the comparison functor.

Returns: Copy of the comparison functor

Definition at line 954 of file tpl_fibonacci_heap.H.

References Aleph::Fibonacci_Heap< T, Compare >::cmp.

Referenced by TEST().

◆ link()

template<typename T , class Compare = Aleph::less<T>>

static void Aleph::Fibonacci_Heap< T, Compare >::link	(	Node *	y,
		Node *	x
	)

inlinestaticprivate

Links two trees of the same degree.

Makes y a child of x. Assumes both are roots and x has the smaller key.

Parameters

y	The node to become a child
x	The node to become the parent

Definition at line 190 of file tpl_fibonacci_heap.H.

References Aleph::Fibonacci_Heap< T, Compare >::Node::child, Aleph::Fibonacci_Heap< T, Compare >::Node::degree, Aleph::Fibonacci_Heap< T, Compare >::Node::left, Aleph::Fibonacci_Heap< T, Compare >::Node::right, and y.

Referenced by Aleph::Fibonacci_Heap< T, Compare >::consolidate().

◆ merge() [1/2]

template<typename T , class Compare = Aleph::less<T>>

void Aleph::Fibonacci_Heap< T, Compare >::merge ( Fibonacci_Heap< T, Compare > && other )

inline

Merges another heap into this one (rvalue version).

Parameters

other Temporary heap whose contents will be transferred.

Note: This overload simply forwards to the lvalue reference version, enabling idioms such as merge(Fibonacci_Heap{...}).

Definition at line 888 of file tpl_fibonacci_heap.H.

References Aleph::maps(), and Aleph::Fibonacci_Heap< T, Compare >::merge().

◆ merge() [2/2]

template<typename T , class Compare = Aleph::less<T>>

void Aleph::Fibonacci_Heap< T, Compare >::merge ( Fibonacci_Heap< T, Compare > & other )

inline

Merges another heap into this one.

All nodes from other are transferred to this heap. The other heap becomes empty after this operation.

Parameters

other The heap to merge (will be emptied)

Note: O(1) time complexity

Warning: Both heaps must use compatible comparison functors.

Definition at line 847 of file tpl_fibonacci_heap.H.

References Aleph::Fibonacci_Heap< T, Compare >::cmp, Aleph::Fibonacci_Heap< T, Compare >::Node::data, Aleph::HTList::is_empty(), Aleph::Fibonacci_Heap< T, Compare >::is_empty(), Aleph::maps(), Aleph::Fibonacci_Heap< T, Compare >::min_node, Aleph::Fibonacci_Heap< T, Compare >::num_nodes, and Aleph::Fibonacci_Heap< T, Compare >::Node::right.

Referenced by Aleph::Fibonacci_Heap< T, Compare >::merge(), and TEST().

◆ operator=() [1/2]

template<typename T , class Compare = Aleph::less<T>>

Fibonacci_Heap & Aleph::Fibonacci_Heap< T, Compare >::operator= ( const Fibonacci_Heap< T, Compare > & )

delete

Copy assignment is disabled (use merge or manual copy)

◆ operator=() [2/2]

template<typename T , class Compare = Aleph::less<T>>

Fibonacci_Heap & Aleph::Fibonacci_Heap< T, Compare >::operator= ( Fibonacci_Heap< T, Compare > && other )

inlinenoexcept

Move assignment operator.

Clears this heap and transfers ownership from other.

Parameters

other The heap to move from

Returns: Reference to this heap

Definition at line 483 of file tpl_fibonacci_heap.H.

References Aleph::Fibonacci_Heap< T, Compare >::clear(), Aleph::Fibonacci_Heap< T, Compare >::cmp, Aleph::Fibonacci_Heap< T, Compare >::consolidate_array_, Aleph::maps(), Aleph::Fibonacci_Heap< T, Compare >::min_node, and Aleph::Fibonacci_Heap< T, Compare >::num_nodes.

◆ pop()

template<typename T , class Compare = Aleph::less<T>>

void Aleph::Fibonacci_Heap< T, Compare >::pop ( )

inline

Definition at line 939 of file tpl_fibonacci_heap.H.

References Aleph::Fibonacci_Heap< T, Compare >::extract_min().

◆ size()

template<typename T , class Compare = Aleph::less<T>>

size_t Aleph::Fibonacci_Heap< T, Compare >::size ( ) const

inlinenoexcept

Returns the number of elements in the heap.

Returns: Number of elements

Note: O(1) time complexity

Definition at line 912 of file tpl_fibonacci_heap.H.

References Aleph::Fibonacci_Heap< T, Compare >::num_nodes.

Referenced by TEST(), TEST(), TEST(), TEST(), TEST(), and TEST().

◆ swap()

template<typename T , class Compare = Aleph::less<T>>

void Aleph::Fibonacci_Heap< T, Compare >::swap ( Fibonacci_Heap< T, Compare > & other )

inlinenoexcept

Swaps contents with another heap.

Exchanges all nodes between this heap and other in O(1) time.

Parameters

other The heap to swap with

Definition at line 505 of file tpl_fibonacci_heap.H.

References Aleph::Fibonacci_Heap< T, Compare >::cmp, Aleph::Fibonacci_Heap< T, Compare >::consolidate_array_, Aleph::maps(), Aleph::Fibonacci_Heap< T, Compare >::min_node, and Aleph::Fibonacci_Heap< T, Compare >::num_nodes.

◆ top()

template<typename T , class Compare = Aleph::less<T>>

const T & Aleph::Fibonacci_Heap< T, Compare >::top ( ) const

inline

Definition at line 944 of file tpl_fibonacci_heap.H.

References Aleph::Fibonacci_Heap< T, Compare >::get_min().

◆ update_key()

template<typename T , class Compare = Aleph::less<T>>

Node * Aleph::Fibonacci_Heap< T, Compare >::update_key	(	Node *	x,
		const T &	k
	)

inline

Updates the key of a node (increase or decrease).

Unlike decrease_key, this method handles both increases and decreases. For increases, it deletes and reinserts the node.

Parameters

x	Handle to the node
k	The new key value

Returns: Handle to the node (may be different if key increased)

Exceptions

std::invalid_argument if x is nullptr

Note: O(1) amortized if decreasing, O(log n) amortized if increasing

Definition at line 734 of file tpl_fibonacci_heap.H.

References ah_invalid_argument_if, Aleph::Fibonacci_Heap< T, Compare >::cmp, Aleph::Fibonacci_Heap< T, Compare >::Node::data, Aleph::Fibonacci_Heap< T, Compare >::decrease_key(), Aleph::Fibonacci_Heap< T, Compare >::delete_node(), Aleph::Fibonacci_Heap< T, Compare >::insert(), and Aleph::maps().

Referenced by TEST().

Friends And Related Symbol Documentation

◆ swap()

template<typename T , class Compare >

void swap	(	Fibonacci_Heap< T, Compare > &	a,
		Fibonacci_Heap< T, Compare > &	b
	)

Definition at line 966 of file tpl_fibonacci_heap.H.

Member Data Documentation

◆ cmp

template<typename T , class Compare = Aleph::less<T>>

Compare Aleph::Fibonacci_Heap< T, Compare >::cmp

private

Comparison functor used to order nodes.

Definition at line 172 of file tpl_fibonacci_heap.H.

Referenced by Aleph::Fibonacci_Heap< T, Compare >::add_to_root_list(), Aleph::Fibonacci_Heap< T, Compare >::consolidate(), Aleph::Fibonacci_Heap< T, Compare >::decrease_key(), Aleph::Fibonacci_Heap< T, Compare >::decrease_key(), Aleph::Fibonacci_Heap< T, Compare >::key_comp(), Aleph::Fibonacci_Heap< T, Compare >::merge(), Aleph::Fibonacci_Heap< T, Compare >::operator=(), Aleph::Fibonacci_Heap< T, Compare >::swap(), and Aleph::Fibonacci_Heap< T, Compare >::update_key().

◆ consolidate_array_

template<typename T , class Compare = Aleph::less<T>>

std::vector<Node *> Aleph::Fibonacci_Heap< T, Compare >::consolidate_array_

private

Reusable scratch array for Fibonacci_Heap::consolidate().

Keeping the buffer as a member avoids heap allocations on every extract_min() call, which keeps amortized costs constant.

Definition at line 180 of file tpl_fibonacci_heap.H.

Referenced by Aleph::Fibonacci_Heap< T, Compare >::Fibonacci_Heap(), Aleph::Fibonacci_Heap< T, Compare >::Fibonacci_Heap(), Aleph::Fibonacci_Heap< T, Compare >::consolidate(), Aleph::Fibonacci_Heap< T, Compare >::operator=(), and Aleph::Fibonacci_Heap< T, Compare >::swap().

◆ MAX_DEGREE

template<typename T , class Compare = Aleph::less<T>>

constexpr size_t Aleph::Fibonacci_Heap< T, Compare >::MAX_DEGREE = 128

staticconstexprprivate

Maximum degree tracked during consolidation.

The degree of any Fibonacci heap root is bounded by log_phi(n). The value 128 comfortably covers heaps larger than 2^64 elements.

Definition at line 168 of file tpl_fibonacci_heap.H.

Referenced by Aleph::Fibonacci_Heap< T, Compare >::Fibonacci_Heap(), Aleph::Fibonacci_Heap< T, Compare >::Fibonacci_Heap(), and Aleph::Fibonacci_Heap< T, Compare >::consolidate().

◆ min_node

template<typename T , class Compare = Aleph::less<T>>

Node* Aleph::Fibonacci_Heap< T, Compare >::min_node = nullptr

private

Pointer to the current minimum root.

Definition at line 170 of file tpl_fibonacci_heap.H.

◆ num_nodes

template<typename T , class Compare = Aleph::less<T>>

size_t Aleph::Fibonacci_Heap< T, Compare >::num_nodes = 0

private

Number of elements stored in the heap.

Definition at line 171 of file tpl_fibonacci_heap.H.

Referenced by Aleph::Fibonacci_Heap< T, Compare >::clear(), Aleph::Fibonacci_Heap< T, Compare >::delete_node(), Aleph::Fibonacci_Heap< T, Compare >::emplace(), Aleph::Fibonacci_Heap< T, Compare >::extract_min(), Aleph::Fibonacci_Heap< T, Compare >::insert(), Aleph::Fibonacci_Heap< T, Compare >::insert(), Aleph::Fibonacci_Heap< T, Compare >::merge(), Aleph::Fibonacci_Heap< T, Compare >::operator=(), Aleph::Fibonacci_Heap< T, Compare >::size(), and Aleph::Fibonacci_Heap< T, Compare >::swap().

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

tpl_fibonacci_heap.H

Classes

Public Types

Public Member Functions

Private Member Functions

Static Private Member Functions

Private Attributes

Static Private Attributes

Related Symbols

Detailed Description

Time Complexities (Amortized)

Usage Example

Implementation Notes

Member Typedef Documentation

◆ handle_type

◆ key_compare

◆ value_type

Constructor & Destructor Documentation

◆ Fibonacci_Heap() [1/4]

◆ Fibonacci_Heap() [2/4]

◆ ~Fibonacci_Heap()

◆ Fibonacci_Heap() [3/4]

◆ Fibonacci_Heap() [4/4]

Member Function Documentation

◆ add_to_root_list()

◆ cascading_cut()

◆ clear()

◆ consolidate()

◆ cut()

◆ decrease_key() [1/2]

◆ decrease_key() [2/2]

◆ delete_all_nodes()

◆ delete_node()

◆ emplace()

◆ empty()

◆ extract_min()

◆ get_min()

◆ get_min_node()

◆ insert() [1/2]

◆ insert() [2/2]

◆ is_empty()

◆ key_comp()

◆ link()

◆ merge() [1/2]

◆ merge() [2/2]

◆ operator=() [1/2]

◆ operator=() [2/2]

◆ pop()

◆ size()

◆ swap()

◆ top()

◆ update_key()

Friends And Related Symbol Documentation

◆ swap()

Member Data Documentation

◆ cmp

◆ consolidate_array_

◆ MAX_DEGREE

◆ min_node

◆ num_nodes