# Priority queue

## General information

Representation invariant

1. The abstract data structure priority queue implements ordered sequences.
2. This abstract data structure is generic and parameterized by a fixed key type $\mathcal{K}$ and a fixed comparison $c$ defined on $\mathcal{K}$.
3. An object with key type $K$ represents a finite, dynamically changing multiset, whose elements are of type $\mathcal{K}$ (the multiset may be empty).
4. Let $K_{1}, K_{2} \in \mathcal{K}$ be two values currently stored in the priority queue object such that $K_{1} \le K_{2}$. Then $K_{1}$ will leave the queue earlier when the method $pop$ is used than $K_{2}$.

Constructor: Gets a comparison $c$ and initializes the queue so as to be empty.

## Method

Name: $push$

Input: A key $K \in \mathcal{K}$.

Output: $\in \N$. A unique and permanent ID that identifies the inserted heap item.

Precondition: -

Postcondition: A new element with the key $K$ is inserted into the queue.

## Method

Name: $pop$

Input: -

Output: $\in \mathcal{K}$. Returns the minimum key $K$ currently within the queue.

Precondition: There should be at least one item left in the queue $n\gt 0$.

Postcondition: The length of the queue is smaller by one and the minimum key $K$ is dequeued.

## Method

Name: $peek$

Input: -

Output: $\in \mathcal{K}$. Returns the minimum key $K$ currently within the queue or $void$ if the queue is empty.

Precondition: -

Postcondition: -

## Method

Name: $decreaseKey$

Input: A natural number $ID \in \N$ presenting the heap item $k$ to be changed, a key $K \in \mathcal{K}$.

Output: -

Precondition:

1. A valid ID currently found within the heap $A$
2. $1 \le ID \le N$
3. $K \le A[Positions[ID]].key$

Postcondition: The heap item $h$ has the new $K$. Its position within the heap afterwards is stored accordingly in $Positions[ID]$ and remains at the same or a higher level than before.