pm::Heap< Policy > Class Template Reference

Inherits Policy.

Public Member Functions
template<typename... Args, typename = std::enable_if_t<std::is_constructible<Policy, Args...>::value>>
	Heap (Args &&... args)
	Create an empty heap.
template<typename... Args, typename = std::enable_if_t<std::is_constructible<Policy, Args...>::value>>
	Heap (size_t expected_qlen, Args &&... args)
void	push (const value_type &elem)
	Add a new element or update the position of the existing one after a key increase/decrease.
const value_type &	top () const
	The currently topmost element.
void	update_top ()
	Sift the topmost element down if its key has been increased.
value_type	pop ()
	Remove the topmost element and return it, adjust the heap.
void	erase (const value_type &elem)
	Remove the element.
value_type	erase_at (Int pos)
	Remove element at the given queue position.

Detailed Description

template<typename Policy>
class pm::Heap< Policy >

Heap (priority queue). The queue is stored in a dynamic array, with element indices inducing an implicit binary tree structure (the child elements of the i-th element have indices 2*i+1 and 2*i+2.)

Template Parameters

Policy

class defining the data types and housekeeping methods:

value_type elements stored in the queue

Int position(value_type) const current position (index) of the element in the heap void update_position(value_type, Int old, Int new) change the current position of stored in/with the element; -1 on any side means "none" <any_type> key(value_type) retrieve the key of the element <any_type> key_comparator() const retrieve the key comparator object

keys, values, and comparator may be passed and/or returned by const reference if desired

Constructor & Destructor Documentation

Heap()

template<typename Policy >

template<typename... Args, typename = std::enable_if_t<std::is_constructible<Policy, Args...>::value>>

pm::Heap< Policy >::Heap ( size_t  expected_qlen, Args &&...  args  )

inlineexplicit

Create an empty heap

Parameters

expected_qlen	expected maximal heap size (helps to avoid extra reallocations)
args	optional arguments for constructing the base Policy

---

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

• lib/core/include/Heap.h