Luedecke at 23:13, 19 June 2015

2015-06-19T23:13:08Z

← 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:05, 1 October 2014

2014-10-01T09:05:53Z

← Older revision		Revision as of 09:05, 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: extra..."

2014-09-30T15:06:45Z

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

New page

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

'''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==
'''Invariant:''' Before and after each iteration:
# The value of <math>N</math> is one less than immediately before the call to this method; one heap item has been removed, namely the one that was at position <math>1</math>
# The heap property is fulfilled for all heap items except for the one at index <math>k</math> (for that one, the heap property may or may not be fulfilled).

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

'''Break condition:''' The heap property is fulfilled by <math>k</math> (note that the heap property is trivially fulfilled by <math>k</math> once <math>2 * k > N</math>).

==Induction basis==
'''Abstract view:'''
# Overwrite <math>TheHeap[1]</math> by <math>TheHeap[N]</math>.
# Decrease <math>N</math> by one.
# Update <math>Positions</math> and <math>Unused</math> accordingly.

'''Implementation:'''
# Insert <math>TheHeap[1].ID</math> in <math>Unused</math>.
# Set <math>TheHeap[1].key := TheHeap[N].key</math>.
# Set <math>TheHeap[1].ID := TheHeap[N].ID</math>.
# Set <math>N := N-1</math>.
# Set <math>Positions[TheHeap[1].ID] := 1</math>.
# Set <math>k := 1</math>.

'''Proof:''' Obvious.

==Induction step==
'''Abstract view:'''
# If the current heap item fulfills the heap property, terminate the algorithm.
# Otherwise, exchange the current heap item with one of its children, viz. the smaller one (ties arbitrarily broken). The index <math>k</math> follows the heap item.

'''Implementation'''
# If <math>2*k>N</math>, terminate the algorithm.
# If <math>2*k+1>N</math>, set <math>k' := 2*k</math>.
# Otherwise, set
## <math>k' := 2*k</math> if <math>TheHeap[2k] \le TheHeap[2k+1]</math>;
## <math>k' := 2*k+1</math>, otherwise.
# If <math>TheHeap[k] \le TheHeap[k']</math>, terminate the algorithm.
# 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 former position <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==

Heap as array: extract minimum - Revision history

Luedecke at 23:13, 19 June 2015

Cuozzo at 09:05, 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: extra..."

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