Bounded priority queue: Difference between revisions

From Algowiki
Jump to navigation Jump to search
 
(13 intermediate revisions by 4 users not shown)
Line 1: Line 1:
__NOTOC__
[[Category:Checkup]]
[[Category:Abstract Data Structure]]
[[Category:Abstract Data Structure]]
[[Category:Sequence]]
[[Category:Sequence]]
[[Category:Heaps]]


== General information ==
== General information ==
'''Representation invariant:'''
'''Representation invariant:'''
# This abstract data structure is [[generic]] and parameterized by a fixed '''key type''' <math>\mathcal{K}</math> and a fixed [[comparison]] <math>c</math> defined on <math>\mathcal{K}</math>.
# This abstract data structure is [[Genericity|generic]] and parameterized by a fixed '''key type''' <math>\mathcal{K}</math> and a fixed [[Genericity#Comparison|comparison]] <math>c</math> defined on <math>\mathcal{K}</math>.
# An object with key type <math>\mathcal{K}</math> represents a finite, dynamically changing [[multiset]], of elements of type <math>\mathcal{K}</math> (the multiset may be empty).
# An object with key type <math>\mathcal{K}</math> represents a finite, dynamically changing [[Sets and sequences#Sets and multisets|multiset]], of elements of type <math>\mathcal{K}</math> (the multiset may be empty).
# An object has two additional attributes, which are natural numbers:
# An object has two additional attributes, which are natural numbers:
## Attribute <math>n</math> stores the current number of elements (in particular, <math>n</math> is dynamically changing).
## Attribute <math>n</math> stores the current number of elements (in particular, <math>n</math> is dynamically changing).
## Attribute <math>N_\text{max}\in\mathrm{N}</math> is the maximum number of elements that can be stored in the queue (<math>N_\text{max}</math> is constant throughout the object's life time).
## Attribute <math>N_\text{max}\in\mathrm{N}</math> is the maximum number of elements that can be stored in the queue (<math>N_\text{max}</math> is constant throughout the object's life time).
# Therefore, at any moment, it is <math>n\le N_\text{max}</math>.
# Therefore, at any moment, it is <math>n\le N_\text{max}</math>.
'''Constructor:''' Gets a [[comparison]] <math>c</math> and a natural number <math>N_\text{max}</math>, and initializes the queue so as to be empty with a maximum capacity of <math>N_\text{max}</math> items.
'''Constructor:''' Gets a [[Genericity#Comparison|comparison]] <math>c</math> and a natural number <math>N_\text{max}</math>, and initializes the queue so as to be empty with a maximum capacity of <math>N_\text{max}</math> items.


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


'''Input:''' A key <math>K\in N_\text{max}</math>
'''Input:''' A key <math>K</math> of type <math>\mathcal{K}</math>


'''Output:''' A unique ID (natural number), which is permanently associated with the inserted key, until the key is extracted from the queue.
'''Output:''' A unique ID (natural number), which is permanently associated with the inserted key, until the key is extracted from the queue.
Line 25: Line 26:


== Method ==
== Method ==
'''Name:''' extract minimum
'''Input:''' -
'''Output:''' Returns the minimum key <math>K</math> that is currently stored in the queue.
'''Precondition:''' It is <math>n>0</math>.
'''Postcondition:''' For the minimum key currently stored in the queue, one occurrence is removed (a.k.a. ''dequeued'').


== Method ==
== Method ==
'''Name:''' find minimum
'''Input:''' -
'''Output:''' Returns the minimum key <math>K</math> currently stored in the queue.
'''Precondition:''' It is <math>n>0</math>.
'''Postcondition:''' -


== Method ==
== Method ==
'''Name:''' decrease key
'''Input:''' A natural number <math>ID</math> and a key <math>K</math> of type <math>\mathcal{K}</math>.
'''Output:''' -
'''Precondition:'''
# The input is the ID of some queue element (returned on insertion).
# The value of <math>K</math> is not larger according to <math>c</math> than the current value of the key to which ID refers.
'''Postcondition:''' The key to which ID refers is now <math>K</math> (the old value of that key is lost).


== Method ==
== Method ==
'''Name:''' number
'''Input:''' -
'''Output:''' The value of attribute <math>n</math>, that is, the number of keys currently stored in the queue.
'''Precondition:''' -
'''Postcondition:''' -


== Known implementations ==
== Known implementations ==
Line 36: Line 75:


== Remark ==
== Remark ==
Usually in applications, the key is actually a pair comprising the key proper and an associated piece of information. In ghis case, the [[Comparison|comparison]] would extract the key proper from each pair and compare the keys proper only.


== Reference ==
== Reference ==

Latest revision as of 06:43, 19 October 2015


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

Name: insert

Input: A key [math]\displaystyle{ K }[/math] of type [math]\displaystyle{ \mathcal{K} }[/math]

Output: A unique ID (natural number), which is permanently associated with the inserted key, until the key is extracted from the queue.

Precondition: It is [math]\displaystyle{ n\lt N_\text{max} }[/math].

Postcondition: The input key [math]\displaystyle{ K }[/math] is inserted into the queue (a.k.a. enqueued).

Method

Name: extract minimum

Input: -

Output: Returns the minimum key [math]\displaystyle{ K }[/math] that is currently stored in the queue.

Precondition: It is [math]\displaystyle{ n\gt 0 }[/math].

Postcondition: For the minimum key currently stored in the queue, one occurrence is removed (a.k.a. dequeued).

Method

Name: find minimum

Input: -

Output: Returns the minimum key [math]\displaystyle{ K }[/math] currently stored in the queue.

Precondition: It is [math]\displaystyle{ n\gt 0 }[/math].

Postcondition: -

Method

Name: decrease key

Input: A natural number [math]\displaystyle{ ID }[/math] and a key [math]\displaystyle{ K }[/math] of type [math]\displaystyle{ \mathcal{K} }[/math].

Output: -

Precondition:

  1. The input is the ID of some queue element (returned on insertion).
  2. The value of [math]\displaystyle{ K }[/math] is not larger according to [math]\displaystyle{ c }[/math] than the current value of the key to which ID refers.

Postcondition: The key to which ID refers is now [math]\displaystyle{ K }[/math] (the old value of that key is lost).

Method

Name: number

Input: -

Output: The value of attribute [math]\displaystyle{ n }[/math], that is, the number of keys currently stored in the queue.

Precondition: -

Postcondition: -

Known implementations

Heap as array

Remark

Usually in applications, the key is actually a pair comprising the key proper and an associated piece of information. In ghis case, the comparison would extract the key proper from each pair and compare the keys proper only.

Reference