Dial implementation: Difference between revisions
Jump to navigation
Jump to search
(Created page with "Category:Checkup Category:Data Structures ==General information== '''Abstract Data Structure:''' Bounded monotonous priority queue '''Implementation Invariant:'''...") |
|||
| Line 7: | Line 7: | ||
# For each object of "Dial implementation", there is | # For each object of "Dial implementation", there is | ||
## a specific '''maximum span of keys''' <math>S_\text{max}\in\mathbb{N}</math>, | ## a specific '''maximum span of keys''' <math>S_\text{max}\in\mathbb{N}</math>, | ||
## an array <math>A</math> with index set <math>\ | ## an array <math>A</math> with index set <math>\{0,\ldots,S-1\}</math> [[Set|sets]] of (key,value)-pairs, | ||
## a '''current position''' <math>P\in\mathbb{N}_{0}</math>, which is dynamically changing, | ## a '''current position''' <math>P\in\mathbb{N}_{0}</math>, which is dynamically changing, | ||
Revision as of 07:44, 7 October 2014
General information
Abstract Data Structure: Bounded monotonous priority queue
Implementation Invariant:
- For each object of "Dial implementation", there is
- a specific maximum span of keys [math]\displaystyle{ S_\text{max}\in\mathbb{N} }[/math],
- an array [math]\displaystyle{ A }[/math] with index set [math]\displaystyle{ \{0,\ldots,S-1\} }[/math] sets of (key,value)-pairs,
- a current position [math]\displaystyle{ P\in\mathbb{N}_{0} }[/math], which is dynamically changing,
All keys at an index of [math]\displaystyle{ A }[/math] are equal. For [math]\displaystyle{ i=P,P+1,P+2,\ldots, }[/math]
In particular, the minimum key is associated with …
Remark
The implementations of the methods Bounded priority queue: number and Bounded priority queue: find minimum are trivial and, hence, left out here.