Heap as array: ascendItem: Difference between revisions

From Algowiki
Jump to navigation Jump to search
(Created page with "Category:Algorithm Category:Method of an implementation of a data structure '''Algorithmic problem:''' Heap as array: ascendItem '''Prerequisites:''...")
 
No edit summary
 
(6 intermediate revisions by 2 users not shown)
Line 1: Line 1:
[[Category:Videos]]
{{#ev:youtube|https://www.youtube.com/watch?v=j-r4YOPFp7E|500|right||frame}}
[[Category:Checkup]]
[[Category:Algorithm]]
[[Category:Algorithm]]
[[Category:Method of an implementation of a data structure]]
[[Category:Method of an implementation of a data structure]]
Line 23: Line 26:
==Induction basis==
==Induction basis==
'''Abstract view:'''
'''Abstract view:'''
# Set <math>\ell</math> to the positions of the heap item to be ascended.
# Set <math>\ell</math> to the position of the heap item to be ascended.
'''Implementation:'''
'''Implementation:'''
# <math>\ell := Positions[ID]</math>
# Retrieve <math>\ell</math> from the index handler.
'''Proof:''' Obvious:
'''Proof:''' Obvious:
==Induction basis==


==Induction step==
==Induction step==
'''Abstract view:'''
# Let <math>h</math> denote the heap item at the position <math>\ell</math>.
# If <math>h</math> is the root or its parent has a lower key than h, terminate algorithm.
# Swap <math>h</math> with its parent.
# Set <math>\ell</math> to the position of its parent (new position of <math>h</math>).
'''Implementation:'''
# <math>h := TheHeap[\ell]</math>
# If <math>\ell = 1</math> or <math>TheHeap[\lfloor \ell /2 \rfloor ].key \le h.key</math>, terminate algorithm
# <math>p := \lfloor \ell /2 \rfloor</math>
# Call <math>swapItems(\ell ,p)</math>
# <math>\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>h.key</math>. We will further assume that only the subtree with the parent of <math>h</math> as its root violates the heap property, to be more exact only the subtree <math>T</math> with <math>h</math>, the parent and the other child violate the property. Restoring the heap property in such a case requires to swap <math>h</math> with its parent (namely the root of <math>T</math>), this is done in step 4. We then have to ensure that the subtree <math>T'</math> with <math>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>\ell</math> the position of the swapped root. The new child and parent pair, <math>h</math> and its previous sibling satisfy the heap property because the key of <math>h</math> is smaller than its previous parent. After at most <math>log n</math> iterations the heap item identified by <math>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==
==Complexity==
'''Statement:''' The asymptotic complexity is in <math>\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>\Theta (log n)</math>.


==Further information==
==Further information==

Latest revision as of 23:12, 19 June 2015

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 position of the heap item to be ascended.

Implementation:

  1. Retrieve [math]\displaystyle{ \ell }[/math] from the index handler.

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