Bounded priority queue: Difference between revisions
No edit summary |
|||
| (One intermediate revision by the same user not shown) | |||
| Line 6: | Line 6: | ||
== General information == | == General information == | ||
'''Representation invariant:''' | '''Representation invariant:''' | ||
# This abstract data structure is [[Genericity|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 == | ||
Latest revision as of 06:43, 19 October 2015
General information
Representation invariant:
- 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].
- 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).
- An object has two additional attributes, which are natural numbers:
- Attribute [math]\displaystyle{ n }[/math] stores the current number of elements (in particular, [math]\displaystyle{ n }[/math] is dynamically changing).
- 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).
- 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:
- The input is the ID of some queue element (returned on insertion).
- 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
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.