Heap as array: descendItem: Difference between revisions
Jump to navigation
Jump to search
(Created page with "__NOTOC__ Category:Algorithm Category:Method of an implementation of a data structure '''Algorithmic problem:''' Heap as array: descendItem '''Prere...") |
|||
| Line 11: | Line 11: | ||
==Abstract view== | ==Abstract view== | ||
'''Invariant:''' After <math>i</math> iterations: | |||
# <math>1 \le \ell \le n</math>. | |||
# The parent's key and its parent's keys of the current heap item <math>h</math> identified by <math>/ell</math> are smaller than the key <math>h.key</math>. | |||
'''Variant:''' | |||
# <math>\ell</math> increases each step and points to a valid position within the heap that is at a lower level than before. | |||
'''Break condition:''' | |||
# <math>(2* \ell \le n \Rightarrow h.key \le TheHeap[2* \ell ].key) \land (2* \ell +1 \le n \Rightarrow h.key \le TheHeap[2* \le +1].key)</math> | |||
==Induction basis== | ==Induction basis== | ||
Revision as of 12:51, 30 September 2014
Algorithmic problem: Heap as array: descendItem
Prerequisites:
Type of algorithm: loop
Auxiliary data: A natural number [math]\displaystyle{ \ell }[/math] denoting a position within the heap.
Abstract view
Invariant: After [math]\displaystyle{ i }[/math] iterations:
- [math]\displaystyle{ 1 \le \ell \le n }[/math].
- The parent's key and its parent's keys of the current heap item [math]\displaystyle{ h }[/math] identified by [math]\displaystyle{ /ell }[/math] are smaller than the key [math]\displaystyle{ h.key }[/math].
Variant:
- [math]\displaystyle{ \ell }[/math] increases each step and points to a valid position within the heap that is at a lower level than before.
Break condition:
- [math]\displaystyle{ (2* \ell \le n \Rightarrow h.key \le TheHeap[2* \ell ].key) \land (2* \ell +1 \le n \Rightarrow h.key \le TheHeap[2* \le +1].key) }[/math]