Bounded priority queue - Revision history

Weihe: /* General information */

2015-10-19T06:43:09Z

General information

← Older revision		Revision as of 06:43, 19 October 2015
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).

2015-10-19T06:42:03Z

General information

← Older revision		Revision as of 06:42, 19 October 2015
Line 12:		Line 12:
	## 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 ==

2014-12-28T14:17:35Z

← Older revision		Revision as of 14:17, 28 December 2014
Line 50:		Line 50:
	'''Name:''' decrease key		'''Name:''' decrease key

	'''Input:''' A natural number <math>ID</math> and a ~~real number~~ <math>x</math>.		'''Input:''' A natural number <math>ID</math> and a key <math>K</math> of type <math>\mathcal{K}</math>.

	'''Output:''' -		'''Output:''' -
Line 56:		Line 56:
	'''Precondition:'''		'''Precondition:'''
	# The input is the ID of some queue element (returned on insertion).		# The input is the ID of some queue element (returned on insertion).
	# The value of <math>x</math> is not larger than the current value of the key to which ID refers.		# 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>x</math> (the old value of that key is lost).		'''Postcondition:''' The key to which ID refers is now <math>K</math> (the old value of that key is lost).

	== Method ==		== Method ==

2014-12-28T14:08:52Z

← Older revision		Revision as of 14:08, 28 December 2014
Line 17:		Line 17:
	'''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.

2014-10-07T07:37:12Z

Remark

← Older revision		Revision as of 07:37, 7 October 2014
Line 75:		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 ==

2014-10-02T22:11:22Z

General information

← Older revision		Revision as of 22:11, 2 October 2014
Line 6:		Line 6:
	== 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 [[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 [[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:

2014-10-01T09:00:57Z

← Older revision		Revision as of 09:00, 1 October 2014
Line 1:		Line 1:
	__NOTOC__		__NOTOC__
	[[Category:Checkup]		[[Category:Checkup]]
	[[Category:Abstract Data Structure]]		[[Category:Abstract Data Structure]]
	[[Category:Sequence]]		[[Category:Sequence]]

2014-10-01T09:00:43Z

← Older revision		Revision as of 09:00, 1 October 2014
Line 1:		Line 1:
	__NOTOC__		__NOTOC__
			[[Category:Checkup]
	[[Category:Abstract Data Structure]]		[[Category:Abstract Data Structure]]
	[[Category:Sequence]]		[[Category:Sequence]]

2014-09-30T18:08:34Z

← Older revision		Revision as of 18:08, 30 September 2014
Line 2:		Line 2:
	[[Category:Abstract Data Structure]]		[[Category:Abstract Data Structure]]
	[[Category:Sequence]]		[[Category:Sequence]]
	~~[[Category:Heaps]]~~

	== General information ==		== General information ==

2014-09-30T09:45:17Z

← Older revision		Revision as of 09:45, 30 September 2014
Line 1:		Line 1:
			__NOTOC__
	[[Category:Abstract Data Structure]]		[[Category:Abstract Data Structure]]
	[[Category:Sequence]]		[[Category:Sequence]]