Heap as array - Revision history

Luedecke at 23:12, 19 June 2015

2015-06-19T23:12:14Z

← Older revision		Revision as of 23:12, 19 June 2015
Line 1:		Line 1:
	[[Category:~~Checkup~~]]		[[Category:Videos]]
			{{#ev:youtube\|https://www.youtube.com/watch?v=j-r4YOPFp7E\|500\|right\|\|frame}}
	[[Category:Data Structures]]		[[Category:Data Structures]]
	==General information==		==General information==

Weihe: /* General information */

2014-10-10T09:02:39Z

General information

← Older revision		Revision as of 09:02, 10 October 2014
Line 14:		Line 14:
	# There is an [[Index handler\|index handler]] <math>IH</math> with maximum size <math>N_\text{max}</math> and value type <math>\{1,\ldots,N_\text{max}\}</math>. For each used index <math>i\in\{1,...,N_\text{max}\}</math>, the associated value is the position of one of the <math>N</math> heap items in <math>TheHeap</math>. As long as this heap item is stored, <math>i</math> is permanently associated with this heap item (and can hence be used to locate and access this heap item at any time). The correspondence between the heap items and these numbers <math>i</math> is one-to-one.		# There is an [[Index handler\|index handler]] <math>IH</math> with maximum size <math>N_\text{max}</math> and value type <math>\{1,\ldots,N_\text{max}\}</math>. For each used index <math>i\in\{1,...,N_\text{max}\}</math>, the associated value is the position of one of the <math>N</math> heap items in <math>TheHeap</math>. As long as this heap item is stored, <math>i</math> is permanently associated with this heap item (and can hence be used to locate and access this heap item at any time). The correspondence between the heap items and these numbers <math>i</math> is one-to-one.
	# '''Heap property:''' For each <math>i\in\{2,...,N\}</math>, it is <math>TheHeap[i].key\ge TheHeap[\lfloor i/2 \rfloor ].key.</math>.		# '''Heap property:''' For each <math>i\in\{2,...,N\}</math>, it is <math>TheHeap[i].key\ge TheHeap[\lfloor i/2 \rfloor ].key.</math>.
	In summary, <math>Positions</math> stores the positions of all heap items, <math>Unused</math> stores all currently unused indexes of <math>Positions</math>, and the ID of each heap item refers back to its corresponding index in <math>Positions</math>.

	The heap property may be viewed as follows: Imagine a [[Directed Tree\|binary tree]] of <math>N</math> nodes such that each height level except for the last one is full, and the last one is filled from left to right. The nodes have pairwise different indexes from <math>\{ 1,...,N \}</math>:		The heap property may be viewed as follows: Imagine a [[Directed Tree\|binary tree]] of <math>N</math> nodes such that each height level except for the last one is full, and the last one is filled from left to right. The nodes have pairwise different indexes from <math>\{ 1,...,N \}</math>:
	# The root is indexed <math>1</math>.		# The root is indexed <math>1</math>.

Weihe: /* General information */

2014-10-10T09:00:38Z

General information

← Older revision		Revision as of 09:00, 10 October 2014
Line 12:		Line 12:
	## a component named <math>ID</math>, which is a [[Numbers#natural numbers\|natural number]] and ranges from <math>1,...,N_\text{max}</math>.		## a component named <math>ID</math>, which is a [[Numbers#natural numbers\|natural number]] and ranges from <math>1,...,N_\text{max}</math>.
	# There is an array <math>TheHeap</math> with index range <math>1,...,N_\text{max}</math> and component type heap item. The '''currently stored items''' are <math>TheHeap[1],...,TheHeap[N]</math>.		# There is an array <math>TheHeap</math> with index range <math>1,...,N_\text{max}</math> and component type heap item. The '''currently stored items''' are <math>TheHeap[1],...,TheHeap[N]</math>.
	~~# There is an array <math>Positions</math> with index range <math>1,...,N_\text{max}</math> and integral components from <math>\{1,...,N_\text{max}\}</math>.~~		# There is an [[Index handler\|index handler]] <math>IH</math> with maximum size <math>N_\text{max}</math> and value type <math>\{1,\ldots,N_\text{max}\}</math>. For each used index <math>i\in\{1,...,N_\text{max}\}</math>, the associated value is the position of one of the <math>N</math> heap items in <math>TheHeap</math>. As long as this heap item is stored, <math>i</math> is permanently associated with this heap item (and can hence be used to locate and access this heap item at any time). The correspondence between the heap items and these numbers <math>i</math> is one-to-one.
	# There is an [[~~Sets and sequences#Ordered and sorted sequences~~\|~~ordered sequence~~]] <math>~~Unused~~</math> ~~of [[Numbers#natural numbers\|natural numbers]], which has length~~ <math>N_\text{max}-N</math> and ~~stores pairwise different numbers from~~ <math>\{1,~~...~~,N_\text{max}\}</math>.
	# For each <math>i\in\{1,...,N_\text{max}\}</math> ~~not in <math>Unused</math>:~~
	~~## <math>Positions[i]</math>~~ is the position of one of the <math>N</math> heap items in <math>TheHeap</math>. As long as this heap item is stored, <math>i</math> is permanently associated with this heap item (and can hence be used to locate and access this heap item at any time). The correspondence between the heap items and these numbers <math>i</math> is one-to-one.
	~~## <math>TheHeap[Positions[i]].ID=i</math>~~.
	# '''Heap property:''' For each <math>i\in\{2,...,N\}</math>, it is <math>TheHeap[i].key\ge TheHeap[\lfloor i/2 \rfloor ].key.</math>.		# '''Heap property:''' For each <math>i\in\{2,...,N\}</math>, it is <math>TheHeap[i].key\ge TheHeap[\lfloor i/2 \rfloor ].key.</math>.
	In summary, <math>Positions</math> stores the positions of all heap items, <math>Unused</math> stores all currently unused indexes of <math>Positions</math>, and the ID of each heap item refers back to its corresponding index in <math>Positions</math>.		In summary, <math>Positions</math> stores the positions of all heap items, <math>Unused</math> stores all currently unused indexes of <math>Positions</math>, and the ID of each heap item refers back to its corresponding index in <math>Positions</math>.

Cuozzo at 09:02, 1 October 2014

2014-10-01T09:02:27Z

← Older revision		Revision as of 09:02, 1 October 2014
Line 1:		Line 1:
			[[Category:Checkup]]
	[[Category:Data Structures]]		[[Category:Data Structures]]
	==General information==		==General information==

Cuozzo: /* General information */

2014-09-30T18:22:08Z

General information

← Older revision		Revision as of 18:22, 30 September 2014
Line 12:		Line 12:
	# There is an array <math>TheHeap</math> with index range <math>1,...,N_\text{max}</math> and component type heap item. The '''currently stored items''' are <math>TheHeap[1],...,TheHeap[N]</math>.		# There is an array <math>TheHeap</math> with index range <math>1,...,N_\text{max}</math> and component type heap item. The '''currently stored items''' are <math>TheHeap[1],...,TheHeap[N]</math>.
	# There is an array <math>Positions</math> with index range <math>1,...,N_\text{max}</math> and integral components from <math>\{1,...,N_\text{max}\}</math>.		# There is an array <math>Positions</math> with index range <math>1,...,N_\text{max}</math> and integral components from <math>\{1,...,N_\text{max}\}</math>.
	# There is an [[ordered sequence]] <math>Unused</math> of [[Numbers#natural numbers\|natural numbers]], which has length <math>N_\text{max}-N</math> and stores pairwise different numbers from <math>\{1,...,N_\text{max}\}</math>.		# There is an [[Sets and sequences#Ordered and sorted sequences\|ordered sequence]] <math>Unused</math> of [[Numbers#natural numbers\|natural numbers]], which has length <math>N_\text{max}-N</math> and stores pairwise different numbers from <math>\{1,...,N_\text{max}\}</math>.
	# For each <math>i\in\{1,...,N_\text{max}\}</math> not in <math>Unused</math>:		# For each <math>i\in\{1,...,N_\text{max}\}</math> not in <math>Unused</math>:
	## <math>Positions[i]</math> is the position of one of the <math>N</math> heap items in <math>TheHeap</math>. As long as this heap item is stored, <math>i</math> is permanently associated with this heap item (and can hence be used to locate and access this heap item at any time). The correspondence between the heap items and these numbers <math>i</math> is one-to-one.		## <math>Positions[i]</math> is the position of one of the <math>N</math> heap items in <math>TheHeap</math>. As long as this heap item is stored, <math>i</math> is permanently associated with this heap item (and can hence be used to locate and access this heap item at any time). The correspondence between the heap items and these numbers <math>i</math> is one-to-one.
Line 19:		Line 19:
	In summary, <math>Positions</math> stores the positions of all heap items, <math>Unused</math> stores all currently unused indexes of <math>Positions</math>, and the ID of each heap item refers back to its corresponding index in <math>Positions</math>.		In summary, <math>Positions</math> stores the positions of all heap items, <math>Unused</math> stores all currently unused indexes of <math>Positions</math>, and the ID of each heap item refers back to its corresponding index in <math>Positions</math>.

	The heap property may be viewed as follows: Imagine a [[binary tree]] of <math>N</math> nodes such that each height level except for the last one is full, and the last one is filled from left to right. The nodes have pairwise different indexes from <math>\{ 1,...,N \}</math>:		The heap property may be viewed as follows: Imagine a [[Directed Tree\|binary tree]] of <math>N</math> nodes such that each height level except for the last one is full, and the last one is filled from left to right. The nodes have pairwise different indexes from <math>\{ 1,...,N \}</math>:
	# The root is indexed <math>1</math>.		# The root is indexed <math>1</math>.
	# For a node with <math>i</math>, the left child (if existing) has index <math>2i</math>, and the right child (if existing) has index <math>2i+1</math>.		# For a node with <math>i</math>, the left child (if existing) has index <math>2i</math>, and the right child (if existing) has index <math>2i+1</math>.

Cuozzo at 18:13, 30 September 2014

2014-09-30T18:13:56Z

← Older revision		Revision as of 18:13, 30 September 2014
Line 1:		Line 1:
	[[Category:Data ~~Structure~~]]		[[Category:Data Structures]]
	==General information==		==General information==
	'''Abstract Data Structure:''' [[Bounded priority queue]]		'''Abstract Data Structure:''' [[Bounded priority queue]]

Cuozzo: /* General information */

2014-09-30T17:44:04Z

General information

← Older revision		Revision as of 17:44, 30 September 2014
Line 9:		Line 9:
	# There is an internal type '''heap item''' with two components:		# There is an internal type '''heap item''' with two components:
	## a component named <math>key</math> of type <math>\mathcal{K}</math>		## a component named <math>key</math> of type <math>\mathcal{K}</math>
	## a component named <math>ID</math>, which is a [[natural numbers\|natural number]] and ranges from <math>1,...,N_\text{max}</math>.		## a component named <math>ID</math>, which is a [[Numbers#natural numbers\|natural number]] and ranges from <math>1,...,N_\text{max}</math>.
	# There is an array <math>TheHeap</math> with index range <math>1,...,N_\text{max}</math> and component type heap item. The '''currently stored items''' are <math>TheHeap[1],...,TheHeap[N]</math>.		# There is an array <math>TheHeap</math> with index range <math>1,...,N_\text{max}</math> and component type heap item. The '''currently stored items''' are <math>TheHeap[1],...,TheHeap[N]</math>.
	# There is an array <math>Positions</math> with index range <math>1,...,N_\text{max}</math> and integral components from <math>\{1,...,N_\text{max}\}</math>.		# There is an array <math>Positions</math> with index range <math>1,...,N_\text{max}</math> and integral components from <math>\{1,...,N_\text{max}\}</math>.
	# There is an [[ordered sequence]] <math>Unused</math> of [[natural numbers]], which has length <math>N_\text{max}-N</math> and stores pairwise different numbers from <math>\{1,...,N_\text{max}\}</math>.		# There is an [[ordered sequence]] <math>Unused</math> of [[Numbers#natural numbers\|natural numbers]], which has length <math>N_\text{max}-N</math> and stores pairwise different numbers from <math>\{1,...,N_\text{max}\}</math>.
	# For each <math>i\in\{1,...,N_\text{max}\}</math> not in <math>Unused</math>:		# For each <math>i\in\{1,...,N_\text{max}\}</math> not in <math>Unused</math>:
	## <math>Positions[i]</math> is the position of one of the <math>N</math> heap items in <math>TheHeap</math>. As long as this heap item is stored, <math>i</math> is permanently associated with this heap item (and can hence be used to locate and access this heap item at any time). The correspondence between the heap items and these numbers <math>i</math> is one-to-one.		## <math>Positions[i]</math> is the position of one of the <math>N</math> heap items in <math>TheHeap</math>. As long as this heap item is stored, <math>i</math> is permanently associated with this heap item (and can hence be used to locate and access this heap item at any time). The correspondence between the heap items and these numbers <math>i</math> is one-to-one.

Cuozzo: /* Remark */

2014-09-30T10:43:12Z

Remark

← Older revision		Revision as of 10:43, 30 September 2014
Line 27:		Line 27:

	==Remark==		==Remark==
	The implementations of the methods [[Bounded priority queue: number]] and [[Bounded priority queue: find minimum]] are trivial and, hence, left out here.		The implementations of the methods [[Bounded priority queue\|Bounded priority queue: number]] and [[Bounded priority queue\|Bounded priority queue: find minimum]] are trivial and, hence, left out here.

	==References==		==References==

Cuozzo at 10:41, 30 September 2014

2014-09-30T10:41:05Z

← Older revision		Revision as of 10:41, 30 September 2014
Line 25:		Line 25:

	In particular, the minimum key is associated with the root.		In particular, the minimum key is associated with the root.

			==Remark==
			The implementations of the methods [[Bounded priority queue: number]] and [[Bounded priority queue: find minimum]] are trivial and, hence, left out here.

			==References==

Cuozzo: /* General information */

2014-09-30T10:38:53Z

General information

← Older revision		Revision as of 10:38, 30 September 2014
Line 17:		Line 17:
	## <math>TheHeap[Positions[i]].ID=i</math>.		## <math>TheHeap[Positions[i]].ID=i</math>.
	# '''Heap property:''' For each <math>i\in\{2,...,N\}</math>, it is <math>TheHeap[i].key\ge TheHeap[\lfloor i/2 \rfloor ].key.</math>.		# '''Heap property:''' For each <math>i\in\{2,...,N\}</math>, it is <math>TheHeap[i].key\ge TheHeap[\lfloor i/2 \rfloor ].key.</math>.
			In summary, <math>Positions</math> stores the positions of all heap items, <math>Unused</math> stores all currently unused indexes of <math>Positions</math>, and the ID of each heap item refers back to its corresponding index in <math>Positions</math>.

			The heap property may be viewed as follows: Imagine a [[binary tree]] of <math>N</math> nodes such that each height level except for the last one is full, and the last one is filled from left to right. The nodes have pairwise different indexes from <math>\{ 1,...,N \}</math>:
			# The root is indexed <math>1</math>.
			# For a node with <math>i</math>, the left child (if existing) has index <math>2i</math>, and the right child (if existing) has index <math>2i+1</math>.
			Now associate the node with index <math>i</math> with the key <math>TheHeap[i].key</math>. Then the heap property says that the key of a node is not larger than the keys of its children. In this case, we say that i fulfills the heap property.

			In particular, the minimum key is associated with the root.