cplib::PairingHeap< T, Comp > Struct Template Reference

Pairing heap, a pointer-based heap supporting efficient merge and decrease-key. More...

#include <pairing_heap.hpp>

Classes
struct	iterator

Public Types
using	size_type = std::size_t
using	node_type = impl::PairingHeapNode< T >

Public Member Functions
size_type	size () const
	Returns the number of elements.
bool	empty () const
	Returns whether the heap is empty.
const T &	top ()
	Returns the top element. The heap must be non-empty.
iterator	begin ()
	Returns an iterator to the top element, or a null-pointer iterator if the heap is empty.
iterator	end ()
	Returns a null-pointer iterator, intended for default value or edge case checking.
iterator	push (const T &t)
	Insert an element into the heap.
iterator	push (T &&t)
	Insert an element into the heap.
template<typename... Args>
iterator	emplace (Args &&... args)
	Construct a new element in place in the heap.
void	pop ()
	Remove the top element from the heap.
void	merge (PairingHeap &&other)
	Merge this heap with another heap.
void	decrease_key (iterator it, const T &new_key)
	Decrease the value of a given element.
void	erase (iterator it)
	Remove an arbitrary element from the heap.

Detailed Description

template<typename T, typename Comp = std::less<T>>
struct cplib::PairingHeap< T, Comp >

Pairing heap, a pointer-based heap supporting efficient merge and decrease-key.

A min-heap with std::priority_queue-like interface and supports efficient merge(), decrease_key() and erase(). The latter two take "iterators" returned by push(). "Iterators" are just read-only pointers and cannot be moved around.

All operators except for pop() finishes in constant time, while pop() can take linear time in the worst case. A certain amortized analysis gives that the amortized cost is \(O(\log N)\) for pop(), \(o(\log N)\) for decrease_key(), and \(O(1)\) for all other operations. See https://en.wikipedia.org/wiki/Pairing_heap for more.

Template Parameters

T	Type of elements.
Comp	Comparison function object. Note that this is a min-heap, as opposed to std::priority_queue, so the element on the top is the smallest element ordered by the comparison function.

Member Function Documentation

decrease_key()

template<typename T , typename Comp = std::less<T>>

void cplib::PairingHeap< T, Comp >::decrease_key ( iterator  it, const T &  new_key  )

inline

Decrease the value of a given element.

The new value must be no greater than the current value compared by Comp. \(O(1)\) worst-case latency and \(o(\log N)\) amortized cost.

emplace()

template<typename T , typename Comp = std::less<T>>

template<typename... Args>

iterator cplib::PairingHeap< T, Comp >::emplace ( Args &&...  args )

inline

Construct a new element in place in the heap.

\(O(1)\) worst-case latency and \(O(\log N)\) amortized cost.

erase()

template<typename T , typename Comp = std::less<T>>

void cplib::PairingHeap< T, Comp >::erase ( iterator  it )

inline

Remove an arbitrary element from the heap.

Equivalent to decrease_key() the element to negative infininty, followed by pop(). The given iterator is invalidated. \(O(N)\) worse-case latency and \(O(\log N)\) amortized cost.

merge()

template<typename T , typename Comp = std::less<T>>

void cplib::PairingHeap< T, Comp >::merge ( PairingHeap< T, Comp > &&  other )

inline

Merge this heap with another heap.

The other heap is emptied and all of its elements are added to this heap. Iterators to elements in the other heap remain valid. \(O(1)\) worst-case latency and amortized cost.

pop()

template<typename T , typename Comp = std::less<T>>

void cplib::PairingHeap< T, Comp >::pop ( )

inline

Remove the top element from the heap.

The heap must be non-empty. The iterator pointing to the top element is invalidated. \(O(N)\) worse-case latency and \(O(\log N)\) amortized cost.

push() [1/2]

template<typename T , typename Comp = std::less<T>>

iterator cplib::PairingHeap< T, Comp >::push ( const T &  t )

inline

Insert an element into the heap.

\(O(1)\) worst-case latency and \(O(\log N)\) amortized cost.

push() [2/2]

template<typename T , typename Comp = std::less<T>>

iterator cplib::PairingHeap< T, Comp >::push ( T &&  t )

inline

Insert an element into the heap.

\(O(1)\) worst-case latency and \(O(\log N)\) amortized cost.

---

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

• src/cplib/order/pairing_heap.hpp