Aleph::Fibonacci_Heap< T, Compare >::Node Struct Reference

Represents a node in the Fibonacci Heap. More...

#include <tpl_fibonacci_heap.H>

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

Public Member Functions
	Node (const T &d)
	Construct a node copying d into the internal storage.
	Node (T &&d) noexcept(std::is_nothrow_move_constructible_v< T >)
	Construct a node moving d into the internal storage.
template<typename Arg , typename... Args, std::enable_if_t<(sizeof...(Args) >=1)||(!std::is_same_v< std::decay_t< Arg >, T > &&!std::is_same_v< std::decay_t< Arg >, Node >), int > = 0>
	Node (Arg &&arg, Args &&... args)
	Perfect-forwarding constructor for in-place construction.

Public Attributes
T	data
	The data stored in this node.
Node *	parent = nullptr
	Parent node (nullptr if root)
Node *	child = nullptr
	Pointer to one child (head of child list)
Node *	left = this
	Left sibling in circular list.
Node *	right = this
	Right sibling in circular list.
size_t	degree = 0
	Number of children.
bool	mark = false
	Has this node lost a child since becoming non-root?

Detailed Description

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

Represents a node in the Fibonacci Heap.

This structure is publicly accessible to allow external algorithms (such as Dijkstra or Prim) to store handles (pointers) to nodes and perform efficient decrease_key operations.

Warning

Users should not modify node fields directly. Use the heap's methods (decrease_key, delete_node) instead.

Definition at line 125 of file tpl_fibonacci_heap.H.

Constructor & Destructor Documentation

Node() [1/3]

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

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

inlineexplicit

Construct a node copying d into the internal storage.

Definition at line 136 of file tpl_fibonacci_heap.H.

Node() [2/3]

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

Aleph::Fibonacci_Heap< T, Compare >::Node::Node ( T &&  d )

inlineexplicitnoexcept

Construct a node moving d into the internal storage.

Definition at line 139 of file tpl_fibonacci_heap.H.

Node() [3/3]

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

template<typename Arg , typename... Args, std::enable_if_t<(sizeof...(Args) >=1)||(!std::is_same_v< std::decay_t< Arg >, T > &&!std::is_same_v< std::decay_t< Arg >, Node >), int > = 0>

Aleph::Fibonacci_Heap< T, Compare >::Node::Node ( Arg &&  arg, Args &&...  args  )

inlineexplicit

Perfect-forwarding constructor for in-place construction.

This overload allows callers of Fibonacci_Heap::emplace() to forward arbitrary constructor arguments for T without creating temporaries.

Template Parameters

Arg	First argument forwarded to the T constructor.
Args	Remaining constructor arguments.

Parameters

arg	First argument forwarded to the stored value.
args	Remaining arguments forwarded to the stored value.

Definition at line 157 of file tpl_fibonacci_heap.H.

Member Data Documentation

child

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

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

Pointer to one child (head of child list)

Definition at line 129 of file tpl_fibonacci_heap.H.

Referenced by Aleph::Fibonacci_Heap< T, Compare >::cut(), Aleph::Fibonacci_Heap< T, Compare >::delete_all_nodes(), Aleph::Fibonacci_Heap< T, Compare >::delete_node(), and Aleph::Fibonacci_Heap< T, Compare >::link().

data

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

T Aleph::Fibonacci_Heap< T, Compare >::Node::data

The data stored in this node.

Definition at line 127 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 >::get_min(), Aleph::Fibonacci_Heap< T, Compare >::merge(), and Aleph::Fibonacci_Heap< T, Compare >::update_key().

degree

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

size_t Aleph::Fibonacci_Heap< T, Compare >::Node::degree = 0

Number of children.

Definition at line 132 of file tpl_fibonacci_heap.H.

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

left

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

Node* Aleph::Fibonacci_Heap< T, Compare >::Node::left = this

Left sibling in circular list.

Definition at line 130 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 >::cut(), Aleph::Fibonacci_Heap< T, Compare >::delete_all_nodes(), Aleph::Fibonacci_Heap< T, Compare >::delete_node(), and Aleph::Fibonacci_Heap< T, Compare >::link().

mark

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

bool Aleph::Fibonacci_Heap< T, Compare >::Node::mark = false

Has this node lost a child since becoming non-root?

Definition at line 133 of file tpl_fibonacci_heap.H.

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

parent

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

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

Parent node (nullptr if root)

Definition at line 128 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 >::cut(), Aleph::Fibonacci_Heap< T, Compare >::decrease_key(), Aleph::Fibonacci_Heap< T, Compare >::decrease_key(), Aleph::Fibonacci_Heap< T, Compare >::delete_node(), and Aleph::Fibonacci_Heap< T, Compare >::extract_min().

right

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

Node* Aleph::Fibonacci_Heap< T, Compare >::Node::right = this

Right sibling in circular list.

Definition at line 131 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 >::cut(), Aleph::Fibonacci_Heap< T, Compare >::delete_all_nodes(), Aleph::Fibonacci_Heap< T, Compare >::delete_node(), Aleph::Fibonacci_Heap< T, Compare >::extract_min(), Aleph::Fibonacci_Heap< T, Compare >::link(), and Aleph::Fibonacci_Heap< T, Compare >::merge().

---

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

• tpl_fibonacci_heap.H