Heap as array: decrease key - Revision history

Luedecke at 23:12, 19 June 2015

2015-06-19T23:12:38Z

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

Cuozzo at 09:04, 1 October 2014

2014-10-01T09:04:33Z

← Older revision		Revision as of 09:04, 1 October 2014
Line 1:		Line 1:
	__NOTOC__		__NOTOC__
			[[Category:Checkup]]
	[[Category:Algorithm]]		[[Category:Algorithm]]
	[[Category: Method of an implementation of a data structure]]		[[Category: Method of an implementation of a data structure]]

Cuozzo: /* Further information */

2014-09-30T12:34:33Z

Further information

← Older revision		Revision as of 12:34, 30 September 2014
Line 53:		Line 53:

	==Further information==		==Further information==
			Note that the loop is identical to the loop in [[Heap as array: insert]].

Cuozzo: /* Complexity */

2014-09-30T12:33:47Z

Complexity

← Older revision		Revision as of 12:33, 30 September 2014
Line 48:		Line 48:

	==Complexity==		==Complexity==
			'''Statement:''' The asymptotic complexity is logarithmic in the worst case.

			'''Proof:''' Obvious.

	==Further information==		==Further information==

Cuozzo: /* Induction step */

2014-09-30T12:30:52Z

Induction step

@@ Line 32: / Line 32: @@
 ==Induction step==
 ==Complexity==
 ==Further information==

Cuozzo: /* Induction basis */

2014-09-30T12:23:20Z

Induction basis

← Older revision		Revision as of 12:23, 30 September 2014
Line 23:		Line 23:

	==Induction basis==		==Induction basis==
			'''Abstract view:''' The heap item is identified and its key is replaced by <math>x</math>.

			'''Implementation:'''
			# Set <math>k := Positions[ID]</math>.
			# Set <math>TheHeap[k].key := x</math>.

			'''Proof:''' Nothing to show.

	==Induction step==		==Induction step==

Cuozzo: /* Abstract view */

2014-09-30T12:20:56Z

Abstract view

← Older revision		Revision as of 12:20, 30 September 2014
Line 13:		Line 13:

	==Abstract view==		==Abstract view==
			'''Invariant:''' Before and after each iteration:
			# The heap property is fulfilled for all heap items except for the one at position <math>\lfloor k/2 \rfloor</math> (for that one, the heap property may or may not be fulfilled).

			'''Variant:''' <math>k</math> is at least halved.

			'''Break condition:''' One of the following two conditions is fulfilled:
			# either it is <math>k = 1</math>;
			# or, otherwise, the heap property is fulfilled by the heap item at position <math>\lfloor k/2 \rfloor</math>.

	==Induction basis==		==Induction basis==

Cuozzo: Created page with "NOTOC Category:Algorithm Category: Method of an implementation of a data structure '''Algorithmic problem:''' Bounded priority queue|Bounded priority queue: decr..."

2014-09-30T12:16:44Z

Created page with "__NOTOC__ Category:Algorithm Category: Method of an implementation of a data structure '''Algorithmic problem:''' Bounded priority queue|Bounded priority queue: decr..."

New page

__NOTOC__
[[Category:Algorithm]]
[[Category: Method of an implementation of a data structure]]
'''Algorithmic problem:''' [[Bounded priority queue|Bounded priority queue: decrease key]]

'''Prerequisites:'''

'''Type of algorithm:''' loop

'''Auxiliary data:'''
# A '''current index''' <math>k \in \mathbb{N}</math>.
# An auxiliary index <math>k' \in \mathbb{N}</math>.

==Abstract view==

==Induction basis==

==Induction step==

==Complexity==

==Further information==