Priority queue

From Algowiki
Jump to: navigation, search

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

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

Method

Name: [math]push[/math]

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

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

Precondition: -

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

Method

Name: [math]pop[/math]

Input: -

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

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

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

Method

Name: [math]peek[/math]

Input: -

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

Precondition: -

Postcondition: -

Method

Name: [math]decreaseKey[/math]

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

Output: -

Precondition:

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

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