# Bounded priority queue

## General information

Representation invariant:

1. This abstract data structure is generic and parameterized by a fixed key type $\mathcal{K}$ and a fixed comparison $c$ defined on $\mathcal{K}$.
2. An object with key type $\mathcal{K}$ represents a finite, dynamically changing multiset, of elements of type $\mathcal{K}$ (the multiset may be empty).
3. An object has two additional attributes, which are natural numbers:
1. Attribute $n$ stores the current number of elements (in particular, $n$ is dynamically changing).
2. Attribute $N_\text{max}\in\mathrm{N}$ is the maximum number of elements that can be stored in the queue ($N_\text{max}$ is constant throughout the object's life time).
4. Therefore, at any moment, it is $n\le N_\text{max}$.

Constructor: Gets a comparison $c$ and a natural number $N_\text{max}$, and initializes the queue so as to be empty with a maximum capacity of $N_\text{max}$ items.

## Method

Name: insert

Input: A key $K$ of type $\mathcal{K}$

Output: A unique ID (natural number), which is permanently associated with the inserted key, until the key is extracted from the queue.

Precondition: It is $n\lt N_\text{max}$.

Postcondition: The input key $K$ is inserted into the queue (a.k.a. enqueued).

## Method

Name: extract minimum

Input: -

Output: Returns the minimum key $K$ that is currently stored in the queue.

Precondition: It is $n\gt 0$.

Postcondition: For the minimum key currently stored in the queue, one occurrence is removed (a.k.a. dequeued).

## Method

Name: find minimum

Input: -

Output: Returns the minimum key $K$ currently stored in the queue.

Precondition: It is $n\gt 0$.

Postcondition: -

## Method

Name: decrease key

Input: A natural number $ID$ and a key $K$ of type $\mathcal{K}$.

Output: -

Precondition:

1. The input is the ID of some queue element (returned on insertion).
2. The value of $K$ is not larger according to $c$ than the current value of the key to which ID refers.

Postcondition: The key to which ID refers is now $K$ (the old value of that key is lost).

## Method

Name: number

Input: -

Output: The value of attribute $n$, that is, the number of keys currently stored in the queue.

Precondition: -

Postcondition: -

## Remark

Usually in applications, the key is actually a pair comprising the key proper and an associated piece of information. In ghis case, the comparison would extract the key proper from each pair and compare the keys proper only.