Bounded priority queue

General information

Representation invariant:

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

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

Method

Name: insert

Input: A key [math]\displaystyle{ K }[/math] of type [math]\displaystyle{ \mathcal{K} }[/math]

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 [math]\displaystyle{ n\lt N_\text{max} }[/math].

Postcondition: The input key [math]\displaystyle{ K }[/math] is inserted into the queue (a.k.a. enqueued).

Method

Name: extract minimum

Input: -

Output: Returns the minimum key [math]\displaystyle{ K }[/math] that is currently stored in the queue.

Precondition: It is [math]\displaystyle{ n\gt 0 }[/math].

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 [math]\displaystyle{ K }[/math] currently stored in the queue.

Precondition: It is [math]\displaystyle{ n\gt 0 }[/math].

Postcondition: -

Method

Name: decrease key

Input: A natural number [math]\displaystyle{ ID }[/math] and a key [math]\displaystyle{ K }[/math] of type [math]\displaystyle{ \mathcal{K} }[/math].

Output: -

Precondition:

1. The input is the ID of some queue element (returned on insertion).
2. The value of [math]\displaystyle{ K }[/math] is not larger according to [math]\displaystyle{ c }[/math] than the current value of the key to which ID refers.

Postcondition: The key to which ID refers is now [math]\displaystyle{ K }[/math] (the old value of that key is lost).

Method

Name: number

Input: -

Output: The value of attribute [math]\displaystyle{ n }[/math], that is, the number of keys currently stored in the queue.

Precondition: -

Postcondition: -

Known implementations

Heap as array

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.