`class PriorityQueue<ValueType>`

This class models a structure called a priority queue in which values are processed in order of priority. As in conventional English usage, lower priority numbers correspond to higher effective priorities, so that a priority 1 item takes precedence over a priority 2 item.

Constructor
PriorityQueue()	O(1)	Initializes a new priority queue, which is initially empty.
Methods
back()	O(1)	Returns the last value in the queue by reference.
changePriority(`value`, `newPriority`)	O(N)	Adjusts an existing value in the queue to have a new specified priority.
clear()	O(1)	Removes all elements from the priority queue.
dequeue()	O(log N)	Removes and returns the highest priority value.
enqueue(`value`, `priority`)	O(log N)	Adds `value` to the queue with the specified priority.
equals(`pq`)	O(N log N)	Returns `true` if the two queues contain the same elements with the same priorities.
front()	O(1)	Returns the first value in the queue by reference.
isEmpty()	O(1)	Returns `true` if the priority queue contains no elements.
peek()	O(1)	Returns the value of highest priority in the queue, without removing it.
peekPriority()	O(1)	Returns the priority of the first element in the queue, without removing it.
size()	O(1)	Returns the number of values in the priority queue.
toString()	O(N)	Converts the queue to a printable string representation.
Operators
`pq1` == `pq1`	O(N log N)	Returns `true` if `pq1` and `pq2` contain the same elements.
`pq1` != `pq2`	O(N log N)	Returns `true` if `pq1` and `pq2` are different.
`ostream` << `pq`	O(N)	Outputs the contents of the queue to the given output stream.
`istream` >> `pq`	O(N log N)	Reads the contents of the given input stream into the queue.

Constructor detail

PriorityQueue();

Initializes a new priority queue, which is initially empty.

Usage:

PriorityQueue<ValueType> pq;

Method detail

ValueType& back();

Returns the last value in the queue by reference.

This function throws an error if the queue is empty.

Usage:

ValueType last = pq.back();

void changePriority(ValueType value, double newPriority);

Adjusts value in the queue to now have the specified new priority, which must be at least as urgent as (≤) that value's previous priority in the queue.

This function throws an error if the element value is not present in the queue, if the new priority passed is not at least as urgent as its current priority, or if NaN (not-a-number) is passed as the priority.

Usage:

pq.changePriority(value, newPriority);

void clear();

Removes all elements from the priority queue.

Usage:

pq.clear();

ValueType dequeue();

Removes and returns the highest priority value. If multiple entries in the queue have the same priority, those values are dequeued in the same order in which they were enqueued.

This function throws an error if the queue is empty.

Usage:

ValueType first = pq.dequeue();

void enqueue(ValueType value, double priority);

Adds value to the queue with the specified priority. Lower priority numbers correspond to higher priorities, which means that all priority 1 elements are dequeued before any priority 2 elements.

Negative priorities are allowed and are not treated differently from other values. That is, a priority of -1 comes before one of 0, which comes before 1, 2, 3, etc.

This function throws an error if NaN (not-a-number) is passed as the priority.

Usage:

pq.enqueue(value, priority);

bool equals(const PriorityQueue& pq) const;

Returns true if the two queues contain exactly the same element values with the same priorities. Identical in behavior to the == operator.

Usage:

if (pq.equals(pq2)) ...

ValueType& front();

Returns the first value in the queue by reference.

This function throws an error if the queue is empty.

Usage:

ValueType first = pq.front();

bool isEmpty() const;

Returns true if the priority queue contains no elements.

Usage:

if (pq.isEmpty()) ...

ValueType peek() const;

Returns the value of highest priority in the queue, without removing it.

This function throws an error if the queue is empty.

Usage:

ValueType first = pq.peek();

double peekPriority() const;

Returns the priority of the first element in the queue, without removing it.

This function throws an error if the queue is empty.

Usage:

double priority = pq.peekPriority();

int size() const;

Returns the number of values in the priority queue.

Usage:

int n = pq.size();

string toString() const;

Converts the queue to a printable string representation. The elements are listed with their priorities first, such as "{pri1:value1, pri2:value2, pri3:value3}" If your project sets the compiler flag PQUEUE_PRINT_IN_HEAP_ORDER, the elements are shown in an unpredictable order. If not, they are listed in increasing order of priority.

Usage:

string str = pq.toString();