Bounded monotonous priority queue: Difference between revisions
Jump to navigation
Jump to search
No edit summary |
|||
| (11 intermediate revisions by the same user not shown) | |||
| Line 5: | Line 5: | ||
== General information == | == General information == | ||
'''Restriction of genericity:''' | |||
The key type is integral. | |||
'''Representation invariant:''' | '''Representation invariant:''' | ||
Identical to [[Bounded priority queue]] | Identical to [[Bounded priority queue]]. | ||
'''Constructor:''' | |||
Identical to [[Bounded priority queue]]. | |||
== Method == | == Method == | ||
| Line 16: | Line 23: | ||
'''Name:''' extract minimum | '''Name:''' extract minimum | ||
Identical to [[Bounded priority queue]] | Identical to [[Bounded priority queue]]. | ||
== Method == | == Method == | ||
'''Name:''' find minimum | '''Name:''' find minimum | ||
Identical to [[Bounded priority queue]] | Identical to [[Bounded priority queue]]. | ||
== Method == | == Method == | ||
'''Name:''' decrease key | '''Name:''' decrease key | ||
Identical to [[Bounded | Identical to [[Bounded priority queue]] except for: | ||
'''Precondition:''' | '''Precondition:''' | ||
# All preconditions of that method in [[Bounded priority queue]] | # 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. | ||
== Method == | == Method == | ||
'''Name:''' number | '''Name:''' number. | ||
Identical to [[Bounded priority queue]] | Identical to [[Bounded priority queue]] | ||
== Known implementations == | == Known implementations == | ||
# All implementations of [[Bounded priority queue]] | # All implementations of [[Bounded priority queue]]. | ||
# [[Dial implementation]] | # [[Dial implementation]]. | ||
== Remark == | == Remark == | ||
If at all, [[Bounded priority queue]] should be derived from Bounded monotonous priority queue rather than the other way round, to avoid a violation of the Liskov substitution principle. | |||
== Reference == | == Reference == | ||
Latest revision as of 14:33, 17 October 2014
General information
Restriction of genericity: The key type is integral.
Representation invariant: Identical to Bounded priority queue.
Constructor: 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 priority 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
If at all, Bounded priority queue should be derived from Bounded monotonous priority queue rather than the other way round, to avoid a violation of the Liskov substitution principle.