Dial implementation: Difference between revisions

From Algowiki
Jump to navigation Jump to search
No edit summary
No edit summary
Line 8: Line 8:
## a specific '''maximum span of keys''' <math>S\in\mathbb{N}</math>,
## a specific '''maximum span of keys''' <math>S\in\mathbb{N}</math>,
## an array <math>A</math> with index set <math>\{0,\ldots,S-1\}</math> and [[Set|sets]] of keys as components,
## an array <math>A</math> with index set <math>\{0,\ldots,S-1\}</math> and [[Set|sets]] of keys as components,
## a '''current position''' <math>P\in\mathbb{N}_{0}</math>, which is dynamically changing,
## a '''current position of the minimum''' <math>P\in\mathbb{N}_{0}</math>, which is dynamically changing,
## '''ToDo:''' extract the positions array and the list of unused orm Heap as array, make it a separate data structure and integrate an object of that data structure here for the decrease key method


All keys at an index of <math>A</math> are equal. For <math>i\in\{0,\ldots,S-1\}\setminus\{P\}</math>, the value of the keys at position $i$ is larger than the value of the keys at index <math>P</math> by exactly <math>(S+i-P)\bmod S</math>. In particular, the minimum keys are at index $P$
All keys at an index of <math>A</math> are equal. For <math>i\in\{0,\ldots,S-1\}\setminus\{P\}</math>, the value of the keys at position $i$ is larger than the value of the keys at index <math>P</math> by exactly <math>(S+i-P)\bmod S</math>.
 
 
== Methods ==
 
# The minimum keys are found at position <math>P</math>. The position is increased in the minimum extraction method by 1 modulo <math>S</math>, when the set at position <math>P</math> becomes empty.
# A key <math>K</math> is inserted at index <math>(S+K-P)\bmod S</math>.
# 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>.


==Remark==
==Remark==

Revision as of 14:58, 8 October 2014

General information

Abstract Data Structure: Bounded monotonous priority queue where [math]\displaystyle{ \mathcal{K} }[/math] is an integral type.

Implementation Invariant:

  1. For each object of "Dial implementation", there is
    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\in\mathbb{N}_{0} }[/math], which is dynamically changing,
    4. ToDo: extract the positions array and the list of unused orm Heap as array, make it a separate data structure and integrate an object of that data structure here for the decrease key method

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


Methods

  1. The minimum keys are found at position [math]\displaystyle{ P }[/math]. The position is increased in the minimum extraction method by 1 modulo [math]\displaystyle{ S }[/math], when the set at position [math]\displaystyle{ P }[/math] becomes empty.
  2. A key [math]\displaystyle{ K }[/math] is inserted at index [math]\displaystyle{ (S+K-P)\bmod S }[/math].
  3. 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].

Remark

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

References