Bounded priority queue

From Algowiki
Jump to navigation Jump to search


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.

Reference