Template Class HeapPriorityQueue

• Defined in File HeapPriorityQueue.h

Nested Relationships

Nested Types

• Struct HeapPriorityQueue::PriorityItem

Class Documentation

template<class T, std::totally_ordered P = int, int D = 2>
class HeapPriorityQueue

a priority queue on a d-ary min-heap of bounded capacity

Public Types

using Item = T

the type of the items

using Priority = P

the type of the priorities

using Handle = PriorityItem*

what insert() gives

using value_type = PriorityItem

using size_type = std::size_t

using difference_type = std::ptrdiff_t

using reference = const PriorityItem&

using const_reference = const PriorityItem&

using const_iterator = IndirectIterator<typename std::vector<PriorityItem*>::const_iterator>

using iterator = const_iterator

Public Functions

explicit HeapPriorityQueue(int n)

PriorityQueue( n ): the empty queue of capacity n.

Pre:

n >= 0

HeapPriorityQueue(const HeapPriorityQueue&) = delete

HeapPriorityQueue &operator=(const HeapPriorityQueue&) = delete

HeapPriorityQueue(HeapPriorityQueue &&other) noexcept

the items of other, which is left empty; its handles stay valid here

HeapPriorityQueue &operator=(HeapPriorityQueue &&other) noexcept

~HeapPriorityQueue()

bool empty(void) const

int size(void) const

int capacity(void) const

const T &min(void) const

the item of smallest priority

Pre:

the queue is not empty

const P &minPriority(void) const

the smallest priority

Pre:

the queue is not empty

T deleteMin(void)

the last leaf goes to the root and down, O( d log_d n ) time; the handle of the item removed is no longer valid

Pre:

the queue is not empty

Post:

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

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

a new leaf goes up, O( log_d n ) time

Pre:

the queue is not full

Post:

one item more, the handle at its place

void decrease(Handle y, const P &p)

lowers the priority of y to p

Pre:

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

Post:

y has priority p, at its place

std::vector<P> priorities(void) const

the heap: the priorities, by their place

inline const_iterator begin(void) const

inline const_iterator end(void) const

inline const_iterator cbegin(void) const

inline const_iterator cend(void) const

Public Static Functions

static inline int parent(int i)

the parent of the place i > 0

static inline int child(int i, int j)

the j-th child, 0 <= j < d, of the place i

struct PriorityItem

the PRIORITYITEM of the book: priority, item, place in the vector

Public Members

P priority

T value

int pos