Bounded monotonous priority queue: Difference between revisions

From Algowiki
Jump to navigation Jump to search
No edit summary
 
(12 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 prority queue]]
Identical to [[Bounded priority queue]].
 
'''Constructor:'''
Identical to [[Bounded priority queue]].


== Method ==
== Method ==
'''Name:''' insert
'''Name:''' insert


Identical to [[Bounded prority queue]]
Identical to [[Bounded priority queue]]


== Method ==
== Method ==
'''Name:''' extract minimum
'''Name:''' extract minimum


Identical to [[Bounded prority queue]]
Identical to [[Bounded priority queue]].


== Method ==
== Method ==
'''Name:''' find minimum
'''Name:''' find minimum


Identical to [[Bounded prority queue]]
Identical to [[Bounded priority queue]].


== Method ==
== Method ==
'''Name:''' decrease key
'''Name:''' decrease key


Identical to [[Bounded prority queue]] except for:
Identical to [[Bounded priority queue]] except for:


'''Precondition:'''
'''Precondition:'''
# All preconditions of that method in [[Bounded prority 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 prority 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 ==
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.
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:

  1. All preconditions of that method in Bounded priority queue.
  2. 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

  1. All implementations of Bounded priority queue.
  2. 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