template<typename IM, bool MIN = true>
class lemon::SimpleBucketHeap< IM, MIN >
This class implements a simplified bucket heap data structure. It does not provide some functionality, but it is faster and simpler than BucketHeap. The main difference is that BucketHeap stores a doubly-linked list for each key while this class stores only simply-linked lists. It supports erasing only for the item having minimum priority and it does not support key increasing and decreasing.
Note that this implementation does not conform to the heap concept due to the lack of some functionality.
- Template Parameters
-
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. |
- See also
- BucketHeap
|
| SimpleBucketHeap (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.
|
|
Prio | operator[] (const Item &i) const |
| The priority of the given item.
|
|
State | state (const Item &i) const |
| Return the state of an item.
|
|
template<typename IM , bool MIN = true>
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.
Enumerator |
---|
IN_HEAP | = 0.
|
PRE_HEAP | = -1.
|
POST_HEAP | = -2.
|