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 [math]\displaystyle{ \mathcal{K} }[/math] and a fixed comparison [math]\displaystyle{ c }[/math] defined on [math]\displaystyle{ \mathcal{K} }[/math].
3. An object with key type [math]\displaystyle{ K }[/math] represents a finite, dynamically changing multiset, whose elements are of type [math]\displaystyle{ \mathcal{K} }[/math] (the multiset may be empty).
4. Let [math]\displaystyle{ K_{1}, K_{2} \in \mathcal{K} }[/math] be two values currently stored in the priority queue object such that [math]\displaystyle{ K_{1} \le K_{2} }[/math]. Then [math]\displaystyle{ K_{1} }[/math] will leave the queue earlier when the method [math]\displaystyle{ pop }[/math] is used than [math]\displaystyle{ K_{2} }[/math].

Constructor: Gets a comparison [math]\displaystyle{ c }[/math] and initializes the queue so as to be empty.

Method

Name: [math]\displaystyle{ push }[/math]

Input: A key [math]\displaystyle{ K \in \mathcal{K} }[/math].

Output: [math]\displaystyle{ \in \N }[/math]. A unique and permanent ID that identifies the inserted heap item.

Precondition: -

Postcondition: A new element with the key [math]\displaystyle{ K }[/math] is inserted into the queue.

Method

Name: [math]\displaystyle{ pop }[/math]

Input: -

Output: [math]\displaystyle{ \in \mathcal{K} }[/math]. Returns the minimum key [math]\displaystyle{ K }[/math] currently within the queue.

Precondition: There should be at least one item left in the queue [math]\displaystyle{ n\gt 0 }[/math].

Postcondition: The length of the queue is smaller by one and the minimum key [math]\displaystyle{ K }[/math] is dequeued.

Method

Name: [math]\displaystyle{ peek }[/math]

Input: -

Output: [math]\displaystyle{ \in \mathcal{K} }[/math]. Returns the minimum key [math]\displaystyle{ K }[/math] currently within the queue or [math]\displaystyle{ void }[/math] if the queue is empty.

Precondition: -

Postcondition: -

Method

Name: [math]\displaystyle{ decreaseKey }[/math]

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

Output: -

Precondition:

1. A valid ID currently found within the heap [math]\displaystyle{ A }[/math]
2. [math]\displaystyle{ 1 \le ID \le N }[/math]
3. [math]\displaystyle{ K \le A[Positions[ID]].key }[/math]

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