pm::Heap< Policy > Class Template Reference

Inherits Policy.

Public Member Functions
	Heap (const Policy &policy_init, size_t expected_qlen=0)
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 key_type comparison keys associated with elements key_comparator_type comparator for the keys

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" key_type key(value_type) retrieve the key of the element key_comparator_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

template<typename Policy >

pm::Heap< Policy >::Heap ( const Policy &  policy_init, size_t  expected_qlen = 0  )

inlineexplicit

Create an empty heap

Parameters

expected_qlen

expected maximal heap size (helps to avoid extra reallocations)

---

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

• lib/core/include/Heap.h