Heap as array: ascendItem

Algorithmic problem: Heap as array: ascendItem

Prerequisites:

Type of algorithm: loop

Auxiliary data:

1. A natural number [math]\displaystyle{ \ell }[/math] denoting a position within the heap.
2. A pointer [math]\displaystyle{ h }[/math] of type heap item.
3. A natural number [math]\displaystyle{ p }[/math] denoting a position within the heap.

Abstract view

Invariant: After [math]\displaystyle{ i }[/math] iterations:

1. [math]\displaystyle{ 1\le \ell \le n }[/math].
2. The left and right child's key and their children's keys of the current heap item [math]\displaystyle{ h }[/math] identified by [math]\displaystyle{ \ell }[/math] are bigger than the key [math]\displaystyle{ h.key }[/math].

Variant:

1. [math]\displaystyle{ \ell }[/math] decreases each step and points to a valid position within the heap that is at a higher level than before.

Break condition:

1. [math]\displaystyle{ \ell = 1 }[/math] or [math]\displaystyle{ TheHeap[\lfloor \ell /2 \rfloor ].key \le TheHeap[\ell].key }[/math]

Induction basis

Abstract view:

1. Set [math]\displaystyle{ \ell }[/math] to the positions of the heap item to be ascended.

Implementation:

1. [math]\displaystyle{ \ell := Positions[ID] }[/math]

Proof: Obvious:

Induction step

Abstract view:

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

Implementation:

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

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 [math]\displaystyle{ h.key }[/math]. We will further assume that only the subtree with the parent of [math]\displaystyle{ h }[/math] as its root violates the heap property, to be more exact only the subtree [math]\displaystyle{ T }[/math] with [math]\displaystyle{ h }[/math], the parent and the other child violate the property. Restoring the heap property in such a case requires to swap [math]\displaystyle{ h }[/math] with its parent (namely the root of [math]\displaystyle{ T }[/math]), this is done in step 4. We then have to ensure that the subtree [math]\displaystyle{ T' }[/math] with [math]\displaystyle{ h }[/math] 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 [math]\displaystyle{ \ell }[/math] the position of the swapped root. The new child and parent pair, [math]\displaystyle{ h }[/math] and its previous sibling satisfy the heap property because the key of [math]\displaystyle{ h }[/math] is smaller than its previous parent. After at most [math]\displaystyle{ log n }[/math] iterations the heap item identified by [math]\displaystyle{ ID }[/math] 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 [math]\displaystyle{ \Theta (log n) }[/math] in the best and worst case.

Proof: Follows immediately from the fact that the height of the heap tree is in [math]\displaystyle{ \Theta (log n) }[/math].