Heap as array: extract minimum

Algorithmic problem: Bounded priority queue: extract minimum

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 value of [math]\displaystyle{ 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]\displaystyle{ 1 }[/math]
2. The heap property is fulfilled for all heap items except for the one at index [math]\displaystyle{ k }[/math] (for that one, the heap property may or may not be fulfilled).

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

Break condition: The heap property is fulfilled by [math]\displaystyle{ k }[/math] (note that the heap property is trivially fulfilled by [math]\displaystyle{ k }[/math] once [math]\displaystyle{ 2 * k \gt N }[/math]).

Induction basis

Abstract view:

1. Overwrite [math]\displaystyle{ TheHeap[1] }[/math] by [math]\displaystyle{ TheHeap[N] }[/math].
2. Decrease [math]\displaystyle{ N }[/math] by one.
3. Update [math]\displaystyle{ Positions }[/math] and [math]\displaystyle{ Unused }[/math] accordingly.

Implementation:

1. Insert [math]\displaystyle{ TheHeap[1].ID }[/math] in [math]\displaystyle{ Unused }[/math].
2. Set [math]\displaystyle{ TheHeap[1].key := TheHeap[N].key }[/math].
3. Set [math]\displaystyle{ TheHeap[1].ID := TheHeap[N].ID }[/math].
4. Set [math]\displaystyle{ N := N-1 }[/math].
5. Set [math]\displaystyle{ Positions[TheHeap[1].ID] := 1 }[/math].
6. Set [math]\displaystyle{ k := 1 }[/math].

Proof: Obvious.

Induction step

Abstract view:

1. If the current heap item fulfills the heap property, terminate the algorithm.
2. Otherwise, exchange the current heap item with one of its children, viz. the smaller one (ties arbitrarily broken). The index [math]\displaystyle{ k }[/math] follows the heap item.

Implementation

1. If [math]\displaystyle{ 2*k\gt N }[/math], terminate the algorithm.
2. If [math]\displaystyle{ 2*k+1\gt N }[/math], set [math]\displaystyle{ k' := 2*k }[/math].
3. Otherwise, set
   1. [math]\displaystyle{ k' := 2*k }[/math] if [math]\displaystyle{ TheHeap[2k] \le TheHeap[2k+1] }[/math];
   2. [math]\displaystyle{ k' := 2*k+1 }[/math], otherwise.
4. If [math]\displaystyle{ TheHeap[k] \le TheHeap[k'] }[/math], terminate the algorithm.
5. Swap [math]\displaystyle{ Positions[TheHeap[k].ID] }[/math] and [math]\displaystyle{ Positions[TheHeap[k'].ID] }[/math].
6. Swap [math]\displaystyle{ TheHeap[k].key }[/math] and [math]\displaystyle{ TheHeap[k'].key }[/math].
7. Swap [math]\displaystyle{ TheHeap[k].ID }[/math] and [math]\displaystyle{ TheHeap[k'].ID }[/math].
8. Set [math]\displaystyle{ k := k' }[/math].

Correctness: Obviously, the heap item at the former position [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.