Dial implementation: Difference between revisions

From Algowiki
Jump to navigation Jump to search
Line 19: Line 19:
# '''Extract minimum:''' The minimum keys are found at position <math>P</math>. If the set at position <math>P</math> is empty after extracting one minimum element, the current position <math>P</math> is increased by 1 modulo <math>S</math>,  
# '''Extract minimum:''' The minimum keys are found at position <math>P</math>. If the set at position <math>P</math> is empty after extracting one minimum element, the current position <math>P</math> is increased by 1 modulo <math>S</math>,  
# '''Insert:''' A key <math>K</math> is inserted at index <math>(S+K-P)\bmod S</math>.
# '''Insert:''' A key <math>K</math> is inserted at index <math>(S+K-P)\bmod S</math>.
# '''Decrease key:''' Decreasing a key value <math>K</math> to value <math>K'</math> amounts to removing the key from the set at index <math>(S+K-P)\bmod S</math> and re-insert it at index <math>(S+K'-P)\bmod S</math>.
# '''Decrease key:''' Decreasing a key value <math>K</math> to value <math>K'</math> amounts to removing the key from the set at index <math>(S+K-P)\bmod S</math> and re-insert it at index <math>(S+K'-P)\bmod S</math>. The set element is retrieved from the index handler.


==Remark==
==Remark==

Revision as of 14:27, 20 October 2014

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