Heap as array: decrease key: Difference between revisions

From Algowiki
Jump to navigation Jump to search
(Created page with "__NOTOC__ Category:Algorithm Category: Method of an implementation of a data structure '''Algorithmic problem:''' Bounded priority queue|Bounded priority queue: decr...")
 
No edit summary
 
(6 intermediate revisions by one other user not shown)
Line 1: Line 1:
__NOTOC__
[[Category:Videos]]
{{#ev:youtube|https://www.youtube.com/watch?v=j-r4YOPFp7E|500|right||frame}}
[[Category:Checkup]]
[[Category:Algorithm]]
[[Category:Algorithm]]
[[Category: Method of an implementation of a data structure]]
[[Category: Method of an implementation of a data structure]]
Line 13: Line 15:


==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==
'''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==
'''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.
# Set <math>k' := \lfloor k/2 \rfloor </math>.
# If <math>TheHeap[k'].key \le TheHeap[k].key</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 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==
==Complexity==
'''Statement:''' The asymptotic complexity is logarithmic in the worst case.
'''Proof:''' Obvious.


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

Latest revision as of 23:12, 19 June 2015

Algorithmic problem: Bounded priority queue: decrease key

Prerequisites:

Type of algorithm: loop

Auxiliary data:

  1. A current index [math]\displaystyle{ k \in \mathbb{N} }[/math].
  2. An auxiliary index [math]\displaystyle{ k' \in \mathbb{N} }[/math].

Abstract view

Invariant: Before and after each iteration:

  1. The heap property is fulfilled for all heap items except for the one at position [math]\displaystyle{ \lfloor k/2 \rfloor }[/math] (for that one, the heap property may or may not be fulfilled).

Variant: [math]\displaystyle{ k }[/math] is at least halved.

Break condition: One of the following two conditions is fulfilled:

  1. either it is [math]\displaystyle{ k = 1 }[/math];
  2. or, otherwise, the heap property is fulfilled by the heap item at position [math]\displaystyle{ \lfloor k/2 \rfloor }[/math].

Induction basis

Abstract view: The heap item is identified and its key is replaced by [math]\displaystyle{ x }[/math].

Implementation:

  1. Set [math]\displaystyle{ k := Positions[ID] }[/math].
  2. Set [math]\displaystyle{ TheHeap[k].key := x }[/math].

Proof: Nothing to show.

Induction step

Abstract view:

  1. If the current heap item has no parent or the parent fulfills the heap property, terminate the algorithm.
  2. Otherwise, exchange the current heap item with its parent. The index [math]\displaystyle{ k }[/math] follows the heap item.

Implementation:

  1. If [math]\displaystyle{ k=1 }[/math], terminate the algorithm.
  2. Set [math]\displaystyle{ k' := \lfloor k/2 \rfloor }[/math].
  3. If [math]\displaystyle{ TheHeap[k'].key \le TheHeap[k].key }[/math], terminate the algorithm.
  4. Swap [math]\displaystyle{ Positions[TheHeap[k].ID] }[/math] and [math]\displaystyle{ Positions[TheHeap[k'].ID] }[/math].
  5. Swap [math]\displaystyle{ TheHeap[k].key }[/math] and [math]\displaystyle{ TheHeap[k'].key }[/math].
  6. Swap [math]\displaystyle{ TheHeap[k].ID }[/math] and [math]\displaystyle{ TheHeap[k'].ID }[/math].
  7. Set [math]\displaystyle{ k := k' }[/math].

Correctness: Obviously, the heap item at the old [math]\displaystyle{ k }[/math] now fulfills the heap property, and the new [math]\displaystyle{ 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: insert.