Concept class describing the main interface of heaps. A heap is a data structure for storing items with specified values called priorities in such a way that finding the item with minimum priority is efficient. In a heap one can change the priority of an item, add or erase an item, etc.
PR | Type of the priority of the items. |
IM | A read and writable item map with int values, used internally to handle the cross references. |
Comp | A functor class for the ordering of the priorities. The default is std::less<PR> . |
#include <lemon/concepts/heap.h>
Public Types | |
enum | State { IN_HEAP = 0, PRE_HEAP = -1, POST_HEAP = -2 } |
Type to represent the states of the items. More... | |
typedef IM | ItemIntMap |
Type of the item-int map. | |
typedef PR | Prio |
Type of the priorities. | |
typedef ItemIntMap::Key | Item |
Type of the items stored in the heap. | |
Public Member Functions | |
Heap (ItemIntMap &map) | |
The constructor. | |
int | size () const |
The number of items stored in the heap. | |
bool | empty () const |
Checks if the heap is empty. | |
void | clear () |
void | push (const Item &i, const Prio &p) |
Inserts an item into the heap with the given priority. | |
Item | top () const |
Returns the item having minimum priority. | |
Prio | prio () const |
The minimum priority. | |
void | pop () |
Removes the item having minimum priority. | |
void | erase (const Item &i) |
Removes an item from the heap. | |
Prio | operator[] (const Item &i) const |
The priority of an item. | |
void | set (const Item &i, const Prio &p) |
Sets the priority of an item or inserts it, if it is not stored in the heap. | |
void | decrease (const Item &i, const Prio &p) |
Decreases the priority of an item to the given value. | |
void | increase (const Item &i, const Prio &p) |
Increases the priority of an item to the given value. | |
State | state (const Item &i) const |
Returns if an item is in, has already been in, or has never been in the heap. | |
void | state (const Item &i, State st) |
Sets the state of an item in the heap. |
enum State |
Each item has a state associated to it. It can be "in heap", "pre heap" or "post heap". The later two are indifferent from the point of view of the heap, but may be useful for the user.
The item-int map must be initialized in such way that it assigns PRE_HEAP
(-1
) to any element to be put in the heap.
Heap | ( | ItemIntMap & | map | ) | [inline, explicit] |
The constructor.
map | A map that assigns int values to keys of type Item . It is used internally by the heap implementations to handle the cross references. The assigned value must be PRE_HEAP (-1 ) for every item. |
int size | ( | ) | const [inline] |
Returns the number of items stored in the heap.
bool empty | ( | ) | const [inline] |
Returns true
if the heap is empty.
void clear | ( | ) |
Makes the heap empty.
Inserts the given item into the heap with the given priority.
i | The item to insert. |
p | The priority of the item. |
Item top | ( | ) | const [inline] |
Returns the item having minimum priority.
Prio prio | ( | ) | const [inline] |
Returns the minimum priority.
void pop | ( | ) | [inline] |
Removes the item having minimum priority.
void erase | ( | const Item & | i | ) | [inline] |
Removes the given item from the heap if it is already stored.
i | The item to delete. |
Returns the priority of the given item.
i | The item. |
i
must be in the heap. This method sets the priority of the given item if it is already stored in the heap. Otherwise it inserts the given item with the given priority.
i | The item. |
p | The priority. |
Decreases the priority of an item to the given value.
i | The item. |
p | The priority. |
i
must be stored in the heap with priority at least p
. Increases the priority of an item to the given value.
i | The item. |
p | The priority. |
i
must be stored in the heap with priority at most p
. This method returns PRE_HEAP
if the given item has never been in the heap, IN_HEAP
if it is in the heap at the moment, and POST_HEAP
otherwise. In the latter case it is possible that the item will get back to the heap again.
i | The item. |