Heap as array: decrease key: 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:''' Bounded priority queue|Bounded priority queue: decr...") |
|||
| Line 13: | Line 13: | ||
==Abstract view== | ==Abstract view== | ||
'''Invariant:''' Before and after each iteration: | |||
# The heap property is fulfilled for all heap items except for the one at position <math>\lfloor k/2 \rfloor</math> (for that one, the heap property may or may not be fulfilled). | |||
'''Variant:''' <math>k</math> is at least halved. | |||
'''Break condition:''' One of the following two conditions is fulfilled: | |||
# either it is <math>k = 1</math>; | |||
# or, otherwise, the heap property is fulfilled by the heap item at position <math>\lfloor k/2 \rfloor</math>. | |||
==Induction basis== | ==Induction basis== | ||
Revision as of 12:20, 30 September 2014
Algorithmic problem: Bounded priority queue: decrease key
Prerequisites:
Type of algorithm: loop
Auxiliary data:
- A current index [math]\displaystyle{ k \in \mathbb{N} }[/math].
- An auxiliary index [math]\displaystyle{ k' \in \mathbb{N} }[/math].
Abstract view
Invariant: Before and after each iteration:
- The heap property is fulfilled for all heap items except for the one at position [math]\displaystyle{ \lfloor k/2 \rfloor }[/math] (for that one, the heap property may or may not be fulfilled).
Variant: [math]\displaystyle{ k }[/math] is at least halved.
Break condition: One of the following two conditions is fulfilled:
- either it is [math]\displaystyle{ k = 1 }[/math];
- or, otherwise, the heap property is fulfilled by the heap item at position [math]\displaystyle{ \lfloor k/2 \rfloor }[/math].