Template Class PairingHeap

Defined in File PairingHeap.h

Nested Relationships

Nested Types

Struct PairingHeap::Node

Class Documentation

template<class T, std::totally_ordered P = int, bool Aux = false> class PairingHeap

a priority queue on a pairing heap, two-pass, or auxiliary two-pass if Aux

Public Types

using Item = T : the type of the items

using Priority = P : the type of the priorities

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

Public Functions

PairingHeap(void) = default

PairingHeap(const PairingHeap&) = delete

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

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

~PairingHeap()

inline bool empty(void) const

inline 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)

a tree of one node linked with the root, or put in the list

Post:: one item more

T deleteMin(void)

the root removed, its children joined by two passes; 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)

x cut with its subtree and linked with the root, or put in the list

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

struct Node

a node of the heap

Public Members

P priority

T value

Node *child = nullptr: the leftmost child

Node *next = nullptr: the right sibling

Node *prev = nullptr: the left sibling, or the parent