Consider the ADT \(\texttt{PQ}\) (priority queue) which is a data structure used by a computer system to deal with processes having each a unique identifier and a priority. It is obvious that the processes having the highest priority will be executed (deleted) first. Processes with equal priority will be executed in FIFO. We assume that the lowest priority is 0.

We are interested in the following operations: create a PQ, add a process to a PQ, delete the process with the highest priority from a PQ, return the identifier of the process with the highest priority, return the maximal priority, test whether a PQ is empty, return the number of processes having a given priority, and return the total number of processes in PQ.

Type: \(\texttt{PQ}\)
Parameter: \(\texttt{Process = (t_identifier, t_priority)}\)
Use: \(\texttt{Boolean, integer}\)

Functions:
\(\begin{array}{p{1cm} l l l l} & \textbf{Create }: & & \rightarrow \texttt{PQ}\\ & \textbf{Add_process}: & \texttt{PQ} \times \texttt{t_identifier} \times \texttt{t_priority} & \rightarrow \texttt{PQ}\\ & \textbf{Delete_process}: & \texttt{PQ} & \rightarrow \texttt{PQ}\\ & \textbf{First}: & \texttt{PQ} & \rightarrow \texttt{t_identifier}\\ & \textbf{max_priority}: & \texttt{PQ} & \rightarrow \texttt{t_priority}\\ & \textbf{isEmpty}: & \texttt{PQ} & \rightarrow \texttt{Boolean}\\ & \textbf{Processes_number}: & \texttt{PQ} \times \texttt{t_priority} & \rightarrow \texttt{integer}\\ & \textbf{total_number}: & \texttt{PQ} & \rightarrow \texttt{integer}\\ \end{array}\)

Constructors: ...
Preconditions:   ...
Axioms: ...

Fill in missing paragraph.

Difficulty level
This exercise is mostly suitable for students 

Constructors: Create, Add_process

Let p be a PQ, pr a piority
Preconditions:
 Delete_process(p), First(p), max_priority(p), Process_number(p,pr) is defined iff not isEmpty(p)
Let 
Axioms:
    * Delete_process(Add_process(p,id,pr)) = p if max_priority(p) < pr, otherwise Add_process(Delete_process(p),id,pr)
    * First(Add_process(p,id,pr)) = id if max_priority(p) < pr, otherwise First(p)
Back to the list of exercises
Looking for a more challenging exercise, try this one !!
Hashing using quadratic probing