Template Class IndexedDaryHeap

Nested Relationships

Nested Types

Class Documentation

template<class K, unsigned D = 4>
class IndexedDaryHeap

a D-ary heap of the ids [ 0 , n ) by their keys, the least on top, with decrease-key

Public Types

using Key = K

the type of the keys

using Item = int

the items of PRIORITYQUEUE: the ids

using Priority = K

and their priorities, the keys

using Handle = int

what insert() gives: the id itself

Public Functions

explicit IndexedDaryHeap(int n = 0)

the empty heap of the ids [ 0 , n )

Pre:

n >= 0

void reset(int n)

the empty heap of the ids [ 0 , n ), the room kept

Pre:

n >= 0

inline int ids(void) const

the number of ids, n

inline bool empty(void) const
inline std::size_t size(void) const
bool contains(int id) const

whether the id is in the heap

Pre:

id in [ 0 , n )

const K &key(int id) const

the key of an id in the heap

Pre:

id is in the heap

void push(int id, const K &k)

inserts the id with the key k

Pre:

id in [ 0 , n ), not in the heap

void decrease(int id, const K &k)

lowers the key of the id to k

Pre:

id is in the heap, k not greater than its key

bool pushOrDecrease(int id, const K &k)

push( id , k ) if the id is not in the heap, decrease( id , k ) if k is less than its key, nothing otherwise; true if the key changed

Pre:

id in [ 0 , n )

const Entry &top(void) const

the item of least key

Pre:

the heap is not empty

Entry pop(void)

removes the item of least key and returns it

Pre:

the heap is not empty

void clear(void)

removes all the items, in O( size() )

inline Handle insert(int id, const K &k)

PRIORITYQUEUE (section 10.1) [see PriorityQueue.h]: push( id , k ), the id its handle.

Pre:

as push()

inline int min(void) const

PRIORITYQUEUE: the id of least key.

Pre:

the heap is not empty

inline int deleteMin(void)

PRIORITYQUEUE: pop(), the id of least key.

Pre:

the heap is not empty

struct Entry

an item: an id with its key

Public Members

K key
int id