#include "priorityqueue.h"

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 more urgent priorities, so that a priority 1 item takes precedence over a priority 2 item. The fundamental priority queue operations are enqueue (add value with assigned priority) and dequeue (remove value with most urgent priority). Both of these operations run in O(logN) time.

Priority queues do not allow access to elements by index, nor can you iterate through the elements using the range-based for loop.
Constructor
PriorityQueue()  O(1) Initializes a new priority queue, which is initially empty.
Methods
changePriority(value, newPriority)  O(N) Reassigns the priority of an existing value in the priority queue.
clear()  O(1) Removes all elements from the priority queue.
dequeue()  O(log N) Removes and returns the frontmost (most urgent) value.
enqueue(value, priority)  O(log N) Adds value to the priority queue with the specified priority.
equals(pq)  O(N log N) Returns true if the two priority queues contain the same elements with the same priorities.
isEmpty()  O(1) Returns true if the priority queue contains no elements.
peek()  O(1) Returns the value of the frontmost (most urgent) element, without removing it.
peekPriority()  O(1) Returns the priority of the frontmost (most urgent) element, without removing it.
size()  O(1) Returns the number of values in the priority queue.
toString()  O(N) Returns a printable string representation of the priority queue.
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 have different contents.
ostream << pq  O(N) Outputs the contents of the priority queue to the given output stream.
istream >> pq  O(NlogN) Reads the contents of the given input stream into the priority queue.

Constructor detail

PriorityQueue();
Initializes a new priority queue, which is initially empty.

Usage:

PriorityQueue<ValueType> pq;

Method detail

void changePriority(ValueType value, double newPriority);
Re-assigns value to the specified newPriority, which must be at least as urgent as (≤) the value's previous priority.

This function raises an error if the value is not present in this priority queue or if the new priority passed is not at least as urgent as its current priority.

Usage:

pq.changePriority(value, newPriority);

void clear();
Removes all elements from the priority queue.

Usage:

pq.clear();

ValueType dequeue();
Removes and returns the frontmost value from the priority queue. The value with the most urgent priority is frontmost. If multiple entries in the queue have the same priority, those values are dequeued in the reverse order in which they were enqueued.

This function throws an error if the queue is empty.

Usage:

ValueType front = pq.dequeue();

void enqueue(const ValueType& value, double priority);
Adds value to the queue with the specified priority. Lower priority numbers correspond to more urgent 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)) ...

bool isEmpty() const;
Returns true if the priority queue contains no elements.

Usage:

if (pq.isEmpty()) ...

const ValueType& peek() const;
Returns the value of the frontmost element, without removing it. In a priority queue, the value with the most urgent priority is frontmost.

This function throws an error if the queue is empty.

Usage:

ValueType front = pq.peek();

double peekPriority() const;
Returns the priority of the frontmost element, without removing it. In a priority queue, the value with the most urgent priority is frontmost.

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;
Returns a printable string representation of the elements in the priority queue. The format is a list of priority-value pairs "{pri1:value1, pri2:value2, pri3:value3}". The order of elements in the list is unpredictable.

Usage:

string str = pq.toString();

ostream& operator<<(const PriorityQueue& pq);
Outputs the contents of pq to the given output stream. The format is the same as specified by toString.

Usage:

cout << queue << endl;

istream& operator>>(PriorityQueue& pq);
Reads the contents of the given input stream into pq. Any previous contents of the priority queue are replaced. The input is expected to be in the form {pri1:value1, pri2:value2} where the elements can be listed in any order. If unable to read a proper priority queue from the stream, the operation results in a stream fail state.

Usage:

if (infile >> queue) ...