Template Class ListPriorityQueue

• Defined in File ListPriorityQueue.h

Class Documentation

template<class T, std::totally_ordered P = int, bool Sorted = true>
class ListPriorityQueue

a priority queue on a list, sorted by priority or not

Public Types

using Item = T

the type of the items

using Priority = P

the type of priorities

using Handle = typename List<Pair>::Pos

the cell of an item

using value_type = Pair

using size_type = std::size_t

using difference_type = std::ptrdiff_t

using reference = const Pair&

using const_reference = const Pair&

using iterator = typename List<Pair>::const_iterator

using const_iterator = typename List<Pair>::const_iterator

Public Functions

bool empty(void) const

int size(void) const

const T &min(void) const

O( 1 ) if sorted, O( n ) otherwise.

Pre:

the queue is not empty

T deleteMin(void)

O( 1 ) if sorted, O( n ) otherwise.

Pre:

the queue is not empty

Post:

one item less, none of smaller priority than the one removed

Handle insert(const T &x, const P &p)

O( n ) if sorted, O( 1 ) otherwise.

Post:

one item more

void decrease(Handle &y, const P &p)

O( n ) if sorted, O( 1 ) otherwise; the handle stays valid.

Pre:

y is an item of this queue and p is not larger than its priority

inline const_iterator begin(void) const

inline const_iterator end(void) const

inline const_iterator cbegin(void) const

inline const_iterator cend(void) const