Template Class FibonacciHeapPriorityQueue

Defined in File FibonacciHeapPriorityQueue.h

Nested Relationships

Nested Types

Class Documentation

template<class T, std::totally_ordered P = int> class FibonacciHeapPriorityQueue

a priority queue on a Fibonacci heap

Public Types

using Item = T : the type of the items

using Priority = P : the type of the priorities

using Handle = Node*: what insert() gives

using value_type = std::pair<const P&, const T&>

using size_type = std::size_t

using difference_type = std::ptrdiff_t

using reference = value_type 

using const_reference = value_type 

using iterator = const_iterator 

Public Functions

FibonacciHeapPriorityQueue(void) = default

FibonacciHeapPriorityQueue(const FibonacciHeapPriorityQueue&) = delete

FibonacciHeapPriorityQueue &operator=(const FibonacciHeapPriorityQueue&) = delete

FibonacciHeapPriorityQueue(FibonacciHeapPriorityQueue &&other) noexcept: the items of other, which is left empty; its handles stay valid here

~FibonacciHeapPriorityQueue()

bool empty(void) const

int size(void) const

const T &min(void) const

Pre:: the heap is not empty

const P &minPriority(void) const

Pre:: the heap is not empty

Handle insert(const T &x, const P &p)

O( 1 ) time: a tree of one node among the roots.

Post:: one item more

T deleteMin(void)

O( log n ) amortized time; the handle of the item is no longer valid.

Pre:: the heap is not empty
Post:: one item less, none of smaller priority than the one removed

void decrease(Handle x, const P &p)

O( 1 ) amortized time.

Pre:: x is a node of this heap and p is not larger than its priority
Post:: x has priority p

inline const_iterator begin(void) const

inline const_iterator end(void) const

inline const_iterator cbegin(void) const

inline const_iterator cend(void) const

class const_iterator

Public Types

using reference = std::pair<const P&, const T&>

using value_type = reference 

using difference_type = std::ptrdiff_t

using iterator_concept = std::forward_iterator_tag

using iterator_category = std::input_iterator_tag

Public Functions

const_iterator(void) = default

inline explicit const_iterator(const Node *min)

inline reference operator*(void) const

inline const_iterator &operator++(void)

inline const_iterator operator++(int)

inline bool operator==(const const_iterator &o) const

struct Node

a node of the heap

Public Members

P priority

T value

Node *parent = nullptr

Node *child = nullptr

Node *left = this

Node *right = this

int degree = 0

bool mark = false