Bounded monotonous priority queue: Difference between revisions

From Algowiki
Jump to navigation Jump to search
m (Protected "Bounded monotonous priority queue" ([Edit=Allow only administrators] (indefinite) [Move=Allow only administrators] (indefinite)))
(No difference)

Revision as of 07:54, 10 October 2014


General information

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