Heap as array: decrease key: Difference between revisions

From Algowiki
Jump to navigation Jump to search
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==

Revision as of 12:23, 30 September 2014

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

Complexity

Further information