Heap as array: insert

Algorithmic problem: Bounded priority queue: insert

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].
3. A number [math]\displaystyle{ ID }[/math] storing the ID to be eventually returned for the new heap element.

Abstract view

Invariant: Before and after each iteration:

1. The value of [math]\displaystyle{ N }[/math] is one higher than immediately before the call to this method; one heap item has been inserted, and the key of this heap item is the input key.
2. 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:

1. Attach the new heap item at position [math]\displaystyle{ N + 1 }[/math].
2. Increase [math]\displaystyle{ N }[/math] by one.
3. Take a position [math]\displaystyle{ i }[/math] from [math]\displaystyle{ Unused }[/math] and associate [math]\displaystyle{ Positions[i] }[/math] with the new heap item.

Implementation:

1. Set [math]\displaystyle{ N:=N+1 }[/math].
2. Set [math]\displaystyle{ TheHeap[N].key:=K }[/math].
3. Extract some [math]\displaystyle{ i }[/math] from [math]\displaystyle{ Unused }[/math].
4. Set [math]\displaystyle{ Positions[i]:=N }[/math].
5. Set [math]\displaystyle{ TheHeap[N].ID:=i }[/math].
6. Set [math]\displaystyle{ ID:=i }[/math].

Proof: Obvious.

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 and return [math]\displaystyle{ ID }[/math].
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 and return [math]\displaystyle{ ID }[/math].
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: decrease key.