Heap as array: ascendItem

Algorithmic problem: Heap as array: ascendItem

Prerequisites:

Type of algorithm: loop

Auxiliary data:

1. A natural number $\ell$ denoting a position within the heap.
2. A pointer $h$ of type heap item.
3. A natural number $p$ denoting a position within the heap.

Abstract view

Invariant: After $i$ iterations:

1. $1\le \ell \le n$.
2. The left and right child's key and their children's keys of the current heap item $h$ identified by $\ell$ are bigger than the key $h.key$.

Variant:

1. $\ell$ decreases each step and points to a valid position within the heap that is at a higher level than before.

Break condition:

1. $\ell =1$ or $TheHeap[\lfloor \ell /2\rfloor ].key\le TheHeap[\ell ].key$

Induction basis

Abstract view:

1. Set $\ell$ to the position of the heap item to be ascended.

Implementation:

1. Retrieve $\ell$ from the index handler.

Proof: Obvious:

Induction step

Abstract view:

1. Let $h$ denote the heap item at the position $\ell$.
2. If $h$ is the root or its parent has a lower key than h, terminate algorithm.
3. Swap $h$ with its parent.
4. Set $\ell$ to the position of its parent (new position of $h$).

Implementation:

1. $h:=TheHeap[\ell ]$
2. If $\ell =1$ or $TheHeap[\lfloor \ell /2\rfloor ].key\le h.key$, terminate algorithm
3. $p:=\lfloor \ell /2\rfloor$
4. Call $swapItems(\ell ,p)$
5. $\ell :=p$

Correctness: If the break condition holds the algorithm is obviously correct, as we already restored the heap property. So consider the case where we have a parent that has a key that is bigger than from $h.key$. We will further assume that only the subtree with the parent of $h$ as its root violates the heap property, to be more exact only the subtree $T$ with $h$, the parent and the other child violate the property. Restoring the heap property in such a case requires to swap $h$ with its parent (namely the root of $T$), this is done in step 4. We then have to ensure that the subtree $T^{\prime }$ with $h$ as a child, its new parent and its sibling also holds the heap property, this step is done by the next iteration and by assigning $\ell$ the position of the swapped root. The new child and parent pair, $h$ and its previous sibling satisfy the heap property because the key of $h$ is smaller than its previous parent. After at most $logn$ iterations the heap item identified by $ID$ is now the new root of the whole tree or has a parent that fulfills the heap property. Therefore the heap property for the whole tree is restored again.

Complexity

Statement: The asymptotic complexity is in $\mathrm{\Theta }(logn)$ in the best and worst case.

Proof: Follows immediately from the fact that the height of the heap tree is in $\mathrm{\Theta }(logn)$.