This class implements the bucket heap data structure. It practically conforms to the heap concept, but it has some limitations.
The bucket heap is a very simple structure. It can store only int
priorities and it maintains a list of items for each priority in the range [0..C)
. So it should only be used when the priorities are small. It is not intended to use as a Dijkstra heap.
IM | A read-writable item map with int values, used internally to handle the cross references. |
MIN | Indicate if the heap is a min-heap or a max-heap. The default is min-heap. If this parameter is set to false , then the comparison is reversed, so the top(), prio() and pop() functions deal with the item having maximum priority instead of the minimum. |
#include <lemon/bucket_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 int | Prio |
Type of the priorities. | |
typedef ItemIntMap::Key | Item |
Type of the items stored in the heap. | |
typedef std::pair< Item, Prio > | Pair |
Type of the item-priority pairs. | |
Public Member Functions | |
BucketHeap (ItemIntMap &map) | |
Constructor. | |
int | size () const |
The number of items stored in the heap. | |
bool | empty () const |
Check if the heap is empty. | |
void | clear () |
Make the heap empty. | |
void | push (const Pair &p) |
Insert a pair of item and priority into the heap. | |
void | push (const Item &i, const Prio &p) |
Insert an item into the heap with the given priority. | |
Item | top () const |
Return the item having minimum priority. | |
Prio | prio () const |
The minimum priority. | |
void | pop () |
Remove the item having minimum priority. | |
void | erase (const Item &i) |
Remove the given item from the heap. | |
Prio | operator[] (const Item &i) const |
The priority of the given item. | |
void | set (const Item &i, const Prio &p) |
Set the priority of an item or insert it, if it is not stored in the heap. | |
void | decrease (const Item &i, const Prio &p) |
Decrease the priority of an item to the given value. | |
void | increase (const Item &i, const Prio &p) |
Increase the priority of an item to the given value. | |
State | state (const Item &i) const |
Return the state of an item. | |
void | state (const Item &i, State st) |
Set 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 latter two are indifferent from the heap's point of view, but may be useful to 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.
BucketHeap | ( | ItemIntMap & | map | ) | [inline, explicit] |
Constructor.
map | A map that assigns int values to the items. It is used internally to handle the cross references. The assigned value must be PRE_HEAP (-1 ) for each item. |
int size | ( | ) | const [inline] |
This function returns the number of items stored in the heap.
bool empty | ( | ) | const [inline] |
This function returns true
if the heap is empty.
void clear | ( | ) | [inline] |
This functon makes the heap empty. It does not change the cross reference map. If you want to reuse a heap that is not surely empty, you should first clear it and then you should set the cross reference map to PRE_HEAP
for each item.
void push | ( | const Pair & | p | ) | [inline] |
This function inserts p.first
to the heap with priority p.second
.
p | The pair to insert. |
p.first
must not be stored in the heap. This function 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] |
This function returns the item having minimum priority.
Prio prio | ( | ) | const [inline] |
This function returns the minimum priority.
void pop | ( | ) | [inline] |
This function removes the item having minimum priority.
void erase | ( | const Item & | i | ) | [inline] |
This function removes the given item from the heap if it is already stored.
i | The item to delete. |
This function returns the priority of the given item.
i | The item. |
This method sets the priority of the given item if it is already stored in the heap. Otherwise it inserts the given item into the heap with the given priority.
i | The item. |
p | The priority. |
This function decreases the priority of an item to the given value.
i | The item. |
p | The priority. |
This function increases the priority of an item to the given value.
i | The item. |
p | The priority. |
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. |