Dial implementation

From Algowiki
Revision as of 14:27, 20 October 2014 by Weihe (talk | contribs) (→‎Methods)
Jump to navigation Jump to search

General information

Abstract data structure: Bounded monotonous priority queue.

Implementation invariant: An object of "Dial implementation" comprises:

  1. A specific maximum span of keys [math]\displaystyle{ S\in\mathbb{N} }[/math].
  2. An array [math]\displaystyle{ A }[/math] with index set [math]\displaystyle{ \{0,\ldots,S-1\} }[/math] and sets of keys as components,
  3. A current position of the minimum [math]\displaystyle{ P }[/math], which is dynamically changing.
  4. An index handler, whose value type is a pointer to an element in a set of keys.

All keys at an index of [math]\displaystyle{ A }[/math] are equal. For [math]\displaystyle{ i\in\{0,\ldots,S-1\} }[/math], the value of the keys at position [math]\displaystyle{ i }[/math] is larger than the value of the keys at index [math]\displaystyle{ P }[/math] by exactly [math]\displaystyle{ (S+i-P)\bmod S }[/math].

For each key currently stored in [math]\displaystyle{ A }[/math], the index handler contains a pointer to the corresponding set element.

Methods

  1. Extract minimum: The minimum keys are found at position [math]\displaystyle{ P }[/math]. If the set at position [math]\displaystyle{ P }[/math] is empty after extracting one minimum element, the current position [math]\displaystyle{ P }[/math] is increased by 1 modulo [math]\displaystyle{ S }[/math],
  2. Insert: A key [math]\displaystyle{ K }[/math] is inserted at index [math]\displaystyle{ (S+K-P)\bmod S }[/math].
  3. Decrease key: Decreasing a key value [math]\displaystyle{ K }[/math] to value [math]\displaystyle{ K' }[/math] amounts to removing the key from the set at index [math]\displaystyle{ (S+K-P)\bmod S }[/math] and re-insert it at index [math]\displaystyle{ (S+K'-P)\bmod S }[/math]. The set element is retrieved from the index handler.

Remark

The implementations of the methods Bounded priority queue: number and Bounded priority queue: find minimum are trivial and, hence, left out here.

References