Luedecke at 23:13, 19 June 2015

2015-06-19T23:13:33Z

← Older revision		Revision as of 23:13, 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:06, 1 October 2014

2014-10-01T09:06:31Z

← Older revision		Revision as of 09:06, 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: Created page with "NOTOC Category:Algorithm Category: Method of an implementation of a data structure '''Algorithmic problem:''' Bounded priority queue|Bounded priority queue: inse..."

2014-09-30T15:35:54Z

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

New page

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

'''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>.
# A number <math>ID</math> storing the ID to be eventually returned for the new heap element.

==Abstract view==
'''Invariant:''' Before and after each iteration:
# The value of <math>N</math> is one higher than immediately before the call to this method; one heap item has been inserted, and the key of this heap item is the input key.
# 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==
'''Abstract view:'''
# Attach the new heap item at position <math>N + 1</math>.
# Increase <math>N</math> by one.
# Take a position <math>i</math> from <math>Unused</math> and associate <math>Positions[i]</math> with the new heap item.

'''Implementation:'''
# Set <math>N:=N+1</math>.
# Set <math>TheHeap[N].key:=K</math>.
# Extract some <math>i</math> from <math>Unused</math>.
# Set <math>Positions[i]:=N</math>.
# Set <math>TheHeap[N].ID:=i</math>.
# Set <math>ID:=i</math>.

'''Proof:''' Obvious.

==Induction step==
'''Abstract view:'''
# If the current heap item has no parent or the parent fulfills the heap property, terminate the algorithm.
# Otherwise, exchange the current heap item with its parent. The index <math>k</math> follows the heap item.

'''Implementation:'''
# If <math>k=1</math>, terminate the algorithm and return <math>ID</math>.
# Set <math>k' := \lfloor k/2 \rfloor </math>.
# If <math>TheHeap[k'].key \le TheHeap[k].key</math>, terminate the algorithm and return <math>ID</math>.
# Swap <math>Positions[TheHeap[k].ID]</math> and <math>Positions[TheHeap[k'].ID]</math>.
# Swap <math>TheHeap[k].key</math> and <math>TheHeap[k'].key</math>.
# Swap <math>TheHeap[k].ID</math> and <math>TheHeap[k'].ID</math>.
# Set <math>k := k'</math>.

'''Correctness:''' Obviously, the heap item at the old <math>k</math> now fulfills the heap property, and the new <math>k</math> is now the only index that does not necessarily fulfill it.

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

'''Proof:''' Obvious.

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

Heap as array: insert - Revision history

Luedecke at 23:13, 19 June 2015

Cuozzo at 09:06, 1 October 2014

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

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