This class implements the Fibonacci heap data structure. 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. CMP
specifies the ordering of the priorities. In a heap one can change the priority of an item, add or erase an item, etc.
The methods increase and erase are not efficient in a Fibonacci heap. In case of many calls to these operations, it is better to use a binary heap.
PRIO | Type of the priority of the items. |
IM | A read and writable Item int map, used internally to handle the cross references. |
CMP | A class for the ordering of the priorities. The default is std::less<PRIO> . |
#include <lemon/fib_heap.h>
Public Types | |
enum | State { IN_HEAP = 0, PRE_HEAP = -1, POST_HEAP = -2 } |
Type to represent the items states. More... | |
typedef IM | ItemIntMap |
| |
typedef PRIO | Prio |
| |
typedef ItemIntMap::Key | Item |
| |
typedef std::pair< Item, Prio > | Pair |
| |
typedef CMP | Compare |
| |
Public Member Functions | |
FibHeap (ItemIntMap &map) | |
The constructor. | |
FibHeap (ItemIntMap &map, const Compare &comp) | |
The constructor. | |
int | size () const |
The number of items stored in the heap. | |
bool | empty () const |
Checks if the heap stores no items. | |
void | clear () |
Make empty this heap. | |
void | set (const Item &item, const Prio &value) |
item gets to the heap with priority value independently if item was already there. | |
void | push (const Item &item, const Prio &value) |
Adds item to the heap with priority value . | |
Item | top () const |
Returns the item with minimum priority relative to Compare . | |
const Prio & | prio () const |
Returns the minimum priority relative to Compare . | |
const Prio & | operator[] (const Item &item) const |
Returns the priority of item . | |
void | pop () |
Deletes the item with minimum priority relative to Compare . | |
void | erase (const Item &item) |
Deletes item from the heap. | |
void | decrease (Item item, const Prio &value) |
Decreases the priority of item to value . | |
void | increase (Item item, const Prio &value) |
Increases the priority of item to value . | |
State | state (const Item &item) const |
Returns if 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 the item in the heap. |
enum State |
Each Item element have a state associated to it. It may 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.
FibHeap | ( | ItemIntMap & | map | ) | [inline, explicit] |
map
should be given to the constructor, since it is used internally to handle the cross references.
FibHeap | ( | ItemIntMap & | map, |
const Compare & | comp | ||
) | [inline] |
map
should be given to the constructor, since it is used internally to handle the cross references. comp
is an object for ordering of the priorities.
int size | ( | ) | const [inline] |
Returns the number of items stored in the heap.
bool empty | ( | ) | const [inline] |
Returns true
if and only if the heap stores no items.
void clear | ( | ) | [inline] |
Make empty this heap. It does not change the cross reference map. If you want to reuse a heap what is not surely empty you should first clear the heap and after that you should set the cross reference map for each item to PRE_HEAP
.
Adds item
to the heap with priority value
.
item
must not be stored in the heap. Item top | ( | ) | const [inline] |
This method returns the item with minimum priority relative to Compare
.
const Prio& prio | ( | ) | const [inline] |
It returns the minimum priority relative to Compare
.
It returns the priority of item
.
item
must be in the heap. void pop | ( | ) | [inline] |
This method deletes the item with minimum priority relative to Compare
from the heap.
void erase | ( | const Item & | item | ) | [inline] |
This method deletes item
from the heap, if item
was already stored in the heap. It is quite inefficient in Fibonacci heaps.
This method decreases the priority of item
to value
.
item
must be stored in the heap with priority at least value
relative to Compare
. This method sets the priority of item
to value
. Though there is no precondition on the priority of item
, this method should be used only if it is indeed necessary to increase (relative to Compare
) the priority of item
, because this method is inefficient.
This method returns PRE_HEAP if 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 item
will get back to the heap again.