Cuozzo: Created page with "NOTOC Category:Checkup Category:Abstract Data Structure Category:Sequence ==General information== '''Representation invariant''' # The abstract data structure..."

2014-10-04T15:33:42Z

Created page with "__NOTOC__ Category:Checkup Category:Abstract Data Structure Category:Sequence ==General information== '''Representation invariant''' # The abstract data structure..."

New page

__NOTOC__
[[Category:Checkup]]
[[Category:Abstract Data Structure]]
[[Category:Sequence]]
==General information==
'''Representation invariant'''
# The abstract data structure '''priority queue''' implements [[Sets and sequences#Ordered and sorted sequences|ordered sequences]].
# 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>K</math> represents a finite, dynamically changing [[Sets and sequences|multiset]], whose elements are of type <math>\mathcal{K}</math> (the multiset may be empty).
# Let <math>K_{1}, K_{2} \in \mathcal{K}</math> be two values currently stored in the priority queue object such that <math>K_{1} \le K_{2}</math>. Then <math>K_{1}</math> will leave the queue earlier when the method <math>pop</math> is used than <math>K_{2}</math>.

'''Constructor:''' Gets a [[Genericity#Comparison|comparison]] <math>c</math> and initializes the queue so as to be empty.

==Method==
'''Name:''' <math>push</math>

'''Input:''' A key <math>K \in \mathcal{K}</math>.

'''Output:''' <math>\in \N</math>. A unique and permanent ID that identifies the inserted heap item.

'''Precondition:''' -

'''Postcondition:''' A new element with the key <math>K</math> is inserted into the queue.

==Method==
'''Name:''' <math>pop</math>

'''Input:''' -

'''Output:''' <math>\in \mathcal{K}</math>. Returns the minimum key <math>K</math> currently within the queue.

'''Precondition:''' There should be at least one item left in the queue <math>n>0</math>.

'''Postcondition:''' The length of the queue is smaller by one and the minimum key <math>K</math> is dequeued.

==Method==
'''Name:''' <math>peek</math>

'''Input:''' -

'''Output:''' <math>\in \mathcal{K}</math>. Returns the minimum key <math>K</math> currently within the queue or <math>void</math> if the queue is empty.

'''Precondition:''' -

'''Postcondition:''' -

==Method==
'''Name:''' <math>decreaseKey</math>

'''Input:''' A natural number <math>ID \in \N</math> presenting the heap item <math>k</math> to be changed, a key <math>K \in \mathcal{K}</math>.

'''Output:''' -

'''Precondition:'''
# A valid ID currently found within the heap <math>A</math>
# <math>1 \le ID \le N</math>
# <math>K \le A[Positions[ID]].key</math>

'''Postcondition:''' The heap item <math>h</math> has the new <math>K</math>. Its position within the heap afterwards is stored accordingly in <math>Positions[ID]</math> and remains at the same or a higher level than before.

Priority queue - Revision history

Cuozzo: Created page with "__NOTOC__ Category:Checkup Category:Abstract Data Structure Category:Sequence ==General information== '''Representation invariant''' # The abstract data structure..."

Cuozzo: Created page with "NOTOC Category:Checkup Category:Abstract Data Structure Category:Sequence ==General information== '''Representation invariant''' # The abstract data structure..."