Heap as array: decrease key

From Algowiki
Jump to: navigation, search

Algorithmic problem: Bounded priority queue: decrease key

Prerequisites:

Type of algorithm: loop

Auxiliary data:

  1. A current index [math]k \in \mathbb{N}[/math].
  2. An auxiliary index [math]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]\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:

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

Induction basis

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

Implementation:

  1. Set [math]k := Positions[ID][/math].
  2. Set [math]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]k[/math] follows the heap item.

Implementation:

  1. If [math]k=1[/math], terminate the algorithm.
  2. Set [math]k' := \lfloor k/2 \rfloor [/math].
  3. If [math]TheHeap[k'].key \le TheHeap[k].key[/math], terminate the algorithm.
  4. Swap [math]Positions[TheHeap[k].ID][/math] and [math]Positions[TheHeap[k'].ID][/math].
  5. Swap [math]TheHeap[k].key[/math] and [math]TheHeap[k'].key[/math].
  6. Swap [math]TheHeap[k].ID[/math] and [math]TheHeap[k'].ID[/math].
  7. 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: insert.