pm::Heap< Key, Params > Class Template Reference

List of all members.

Public Member Functions
	Heap (int expected_qlen=0)
	Heap (const comparator_type &cmp_arg, int expected_qlen=0)
	Create an empty heap, comparator as a copy of the given object.
heap_element_state	get_state (key_arg_type k) const
	Look up the element.
void	push (key_arg_type)
key_arg_type	top () const
	The currently topmost element.
void	update_top ()
	Sift the topmost element down if its priority has been increased.
key_type	pop ()
	Remove the topmost element and return it, adjust the heap.
void	erase (key_arg_type)
	Remove the element.

---

Detailed Description

template<typename Key, typename Params = void>
class pm::Heap< Key, Params >

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.) The elements are mapped to their indices via a hash table.

Parameters:

	Key	elements stored in the heap
	Params	tagged typelist: parameters for fine-tuning Comparator<.> key comparator; default is polymake::operations::cmp (in the most cases it will use the standard relational operators Adapter<.> some class defining the meta-constructors for property maps

---

Constructor & Destructor Documentation

template<typename Key, typename Params = void>

pm::Heap< Key, Params >::Heap

(

int

expected_qlen = 0

)

[inline, explicit]

Create an empty heap, comparator with its default constructor.

Parameters:

expected_qlen

expected maximal heap size (helps to avoid extra reallocations)

---

Member Function Documentation

template<typename Key, typename Params>

void pm::Heap< Key, Params >::push

(

key_arg_type

k

)

[inline]

Add a new element or update its position in the queue. In the latter case it is assumed that its priority has been decreased, this method does not check the opposite case!

---

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

• include/core/polymake/Heap.h