Heap as array: decrease key

Algorithmic problem: Bounded priority queue: decrease key

Prerequisites:

Type of algorithm: loop

Auxiliary data:

1. A current index $k \in \mathbb{N}$.
2. An auxiliary index $k' \in \mathbb{N}$.

Abstract view

Invariant: Before and after each iteration:

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

Variant: $k$ is at least halved.

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

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

Induction basis

Abstract view: The heap item is identified and its key is replaced by $x$.

Implementation:

1. Set $k := Positions[ID]$.
2. Set $TheHeap[k].key := x$.

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 $k$ follows the heap item.

Implementation:

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

Correctness: Obviously, the heap item at the old $k$ now fulfills the heap property, and the new $k$ 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.