Bounded monotonous priority queue: Difference between revisions
Jump to navigation
Jump to search
(Created page with "Test") |
|||
| (13 intermediate revisions by the same user not shown) | |||
| Line 1: | Line 1: | ||
__NOTOC__ | |||
[[Category:Checkup]] | |||
[[Category:Abstract Data Structure]] | |||
[[Category:Sequence]] | |||
== 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>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. | |||
== 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.