Bounded priority queue

From Algowiki
Revision as of 20:40, 29 September 2014 by Cuozzo (talk | contribs)
Jump to navigation Jump to search


General information

Representation invariant:

  1. This abstract data structure is generic and parameterized by a fixed key type [math]\displaystyle{ \mathcal{K} }[/math] and a fixed comparison [math]\displaystyle{ c }[/math] defined on [math]\displaystyle{ \mathcal{K} }[/math].
  2. An object with key type [math]\displaystyle{ \mathcal{K} }[/math] represents a finite, dynamically changing multiset, of elements of type [math]\displaystyle{ \mathcal{K} }[/math] (the multiset may be empty).
  3. An object has two additional attributes, which are natural numbers:
    1. Attribute [math]\displaystyle{ n }[/math] stores the current number of elements (in particular, [math]\displaystyle{ n }[/math] is dynamically changing).
    2. Attribute [math]\displaystyle{ N_\text{max}\in\mathrm{N} }[/math] is the maximum number of elements that can be stored in the queue ([math]\displaystyle{ N_\text{max} }[/math] is constant throughout the object's life time).
  4. Therefore, at any moment, it is [math]\displaystyle{ n\le N_\text{max} }[/math].

Constructor: Gets a comparison [math]\displaystyle{ c }[/math] and a natural number [math]\displaystyle{ N_\text{max} }[/math], and initializes the queue so as to be empty with a maximum capacity of [math]\displaystyle{ N_\text{max} }[/math] items.

Method

Method

Method

Method

Method

Known implementations

Heap as array

Remark

Reference