Heap as array: ascendItem: Difference between revisions

From Algowiki
Jump to navigation Jump to search
mNo edit summary
Line 1: Line 1:
__NOTOC__
__NOTOC__
[[Category:Checkup]]
[[Category:Algorithm]]
[[Category:Algorithm]]
[[Category:Method of an implementation of a data structure]]
[[Category:Method of an implementation of a data structure]]

Revision as of 09:03, 1 October 2014

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].

Further information