template<typename PR, typename IM, int D, typename CMP>
class lemon::DHeap< PR, IM, D, CMP >
This class implements the D-ary heap data structure. It fully conforms to the heap concept.
The D-ary heap is a generalization of the binary heap structure, its nodes have at most D
children, instead of two. BinHeap and QuadHeap are specialized implementations of this structure for D=2
and D=4
, respectively.
- Template Parameters
-
PR | Type of the priorities of the items. |
IM | A read-writable item map with int values, used internally to handle the cross references. |
D | The degree of the heap, each node have at most D children. The default is 16. Powers of two are suggested to use so that the multiplications and divisions needed to traverse the nodes of the heap could be performed faster. |
CMP | A functor class for comparing the priorities. The default is std::less<PR> . |
- See also
- BinHeap
-
FouraryHeap
|
| DHeap (ItemIntMap &map) |
| Constructor.
|
|
| DHeap (ItemIntMap &map, const Compare &comp) |
| 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.
|
|
void | replace (const Item &i, const Item &j) |
| Replace an item in the heap.
|
|
template<typename PR , typename IM , int D, typename CMP >
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.
|
template<typename PR , typename IM , int D, typename CMP >
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.
template<typename PR , typename IM , int D, typename CMP >
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.
- Parameters
-
template<typename PR , typename IM , int D, typename CMP >
void replace |
( |
const Item & |
i, |
|
|
const Item & |
j |
|
) |
| |
|
inline |
This function replaces item i
with item j
. Item i
must be in the heap, while j
must be out of the heap. After calling this method, item i
will be out of the heap and j
will be in the heap with the same prioriority as item i
had before.