Detailed Description
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
#include <lemon/dheap.h>
List of all members.
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.
|
typedef std::pair< Item, Prio > | Pair |
| Type of the item-priority pairs.
|
typedef CMP | Compare |
| Functor type for comparing the priorities.
|
Public Member Functions |
| 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.
|
Member Enumeration Documentation
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.
|
Constructor & Destructor Documentation
Constructor.
- Parameters:
-
| 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. |
Constructor.
- Parameters:
-
| 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. |
| comp | The function object used for comparing the priorities. |
Member Function Documentation
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.
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
.
- Parameters:
-
- Precondition:
p.first
must not be stored in the heap.
void push |
( |
const Item & |
i, |
|
|
const Prio & |
p | |
|
) |
| | [inline] |
This function inserts the given item into the heap with the given priority.
- Parameters:
-
| i | The item to insert. |
| p | The priority of the item. |
- Precondition:
- i must not be stored in the heap.
Item top |
( |
|
) |
const [inline] |
This function returns the item having minimum priority.
- Precondition:
- The heap must be non-empty.
Prio prio |
( |
|
) |
const [inline] |
This function returns the minimum priority.
- Precondition:
- The heap must be non-empty.
This function removes the item having minimum priority.
- Precondition:
- The heap must be non-empty.
void erase |
( |
const Item & |
i |
) |
[inline] |
This function removes the given item from the heap if it is already stored.
- Parameters:
-
- Precondition:
- i must be in the heap.
Prio operator[] |
( |
const Item & |
i |
) |
const [inline] |
This function returns the priority of the given item.
- Parameters:
-
- Precondition:
- i must be in the heap.
void set |
( |
const Item & |
i, |
|
|
const Prio & |
p | |
|
) |
| | [inline] |
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.
- Parameters:
-
| i | The item. |
| p | The priority. |
void decrease |
( |
const Item & |
i, |
|
|
const Prio & |
p | |
|
) |
| | [inline] |
This function decreases the priority of an item to the given value.
- Parameters:
-
| i | The item. |
| p | The priority. |
- Precondition:
- i must be stored in the heap with priority at least p.
void increase |
( |
const Item & |
i, |
|
|
const Prio & |
p | |
|
) |
| | [inline] |
This function increases the priority of an item to the given value.
- Parameters:
-
| i | The item. |
| p | The priority. |
- Precondition:
- i must be stored in the heap with priority at most p.
State state |
( |
const Item & |
i |
) |
const [inline] |
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:
-
void state |
( |
const Item & |
i, |
|
|
State |
st | |
|
) |
| | [inline] |
This function sets the state of the given item in the heap. It can be used to manually clear the heap when it is important to achive better time complexity.
- Parameters:
-
| i | The item. |
| st | The state. It should not be IN_HEAP . |
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.