Bounded monotonous priority queue: Difference between revisions
Jump to navigation
Jump to search
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:''' | '''Constructor:''' |
Revision as of 07:56, 10 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.