Bounded monotonous priority queue: Difference between revisions
Jump to navigation
Jump to search
No edit summary |
No edit summary |
||
| Line 6: | Line 6: | ||
== General information == | == General information == | ||
'''Representation invariant:''' | '''Representation invariant:''' | ||
Identical to [[Bounded | Identical to [[Bounded priority queue]] | ||
== Method == | == Method == | ||
'''Name:''' insert | '''Name:''' insert | ||
Identical to [[Bounded | Identical to [[Bounded priority queue]] | ||
== Method == | == Method == | ||
'''Name:''' extract minimum | '''Name:''' extract minimum | ||
Identical to [[Bounded | Identical to [[Bounded priority queue]] | ||
== Method == | == Method == | ||
'''Name:''' find minimum | '''Name:''' find minimum | ||
Identical to [[Bounded | Identical to [[Bounded priority queue]] | ||
== Method == | == Method == | ||
| Line 29: | Line 29: | ||
'''Precondition:''' | '''Precondition:''' | ||
# All preconditions of that method in [[Bounded | # All preconditions of that method in [[Bounded priority queue]] | ||
# The value of <math>x</math> is not smaller than the current minimum value. | # The value of <math>x</math> is not smaller than the current minimum value. | ||
| Line 35: | Line 35: | ||
'''Name:''' number | '''Name:''' number | ||
Identical to [[Bounded | Identical to [[Bounded priority queue]] | ||
== Known implementations == | == Known implementations == | ||
Revision as of 06:51, 7 October 2014
General information
Representation invariant: Identical to Bounded priority queue
Method
Name: insert
Identical to Bounded priority queue
Method
Name: extract minimum
Identical to Bounded priority queue
Method
Name: find minimum
Identical to Bounded priority queue
Method
Name: decrease key
Identical to Bounded prority queue except for:
Precondition:
- All preconditions of that method in Bounded priority queue
- The value of [math]\displaystyle{ x }[/math] is not smaller than the current minimum value.
Method
Name: number
Identical to Bounded priority queue
Known implementations
- All implementations of Bounded priority queue
- Dial implementation
Remark
As the known implementations show, Bounded priority queue should be derived Bounded monotonous priority queue rather than the other way round, to avoid a violation of the Liskov substitution principle.