Heap as array: Difference between revisions

From Algowiki
Jump to navigation Jump to search
(Created page with "Category:Data Structure ==General information== '''Abstract Data Structure:''' Bounded priority queue '''Implementation Invariant:''' # For each object of "Heap as arr...")
 
Line 2: Line 2:
==General information==
==General information==
'''Abstract Data Structure:''' [[Bounded priority queue]]
'''Abstract Data Structure:''' [[Bounded priority queue]]
'''Implementation Invariant:'''
'''Implementation Invariant:'''
# For each object of "Heap as array", there is
# For each object of "Heap as array", there is

Revision as of 10:20, 30 September 2014

General information

Abstract Data Structure: Bounded priority queue

Implementation Invariant:

  1. For each object of "Heap as array", there is
    1. a specific maximum number of items [math]\displaystyle{ N_\text{max}\in\mathbb{N} }[/math], which is constant throughout the object's lifetime.
    2. a current number of items [math]\displaystyle{ N\in\mathbb{N}_{0} }[/math], which is dynamically changing, but it is [math]\displaystyle{ N\le N_\text{max} }[/math] at any time.
  2. There is an internal type heap item with two components:
    1. a component named [math]\displaystyle{ key }[/math] of type [math]\displaystyle{ \mathcal{K} }[/math]
    2. a component named [math]\displaystyle{ ID }[/math], which is a natural number and ranges from [math]\displaystyle{ 1,...,N_\text{max} }[/math].
  3. There is an array [math]\displaystyle{ TheHeap }[/math] with index range [math]\displaystyle{ 1,...,N_\text{max} }[/math] and component type heap item. The currently stored items are [math]\displaystyle{ TheHeap[1],...,TheHeap[N] }[/math].
  4. There is an array [math]\displaystyle{ Positions }[/math] with index range [math]\displaystyle{ 1,...,N_\text{max} }[/math] and integral components from [math]\displaystyle{ \{1,...,N_\text{max}\} }[/math].
  5. There is an ordered sequence [math]\displaystyle{ Unused }[/math] of natural numbers, which has length [math]\displaystyle{ N_\text{max}-N }[/math] and stores pairwise different numbers from [math]\displaystyle{ \{1,...,N_\text{max}\} }[/math].
  6. For each [math]\displaystyle{ i\in\{1,...,N_\text{max}\} }[/math] not in [math]\displaystyle{ Unused }[/math]:
    1. [math]\displaystyle{ Positions[i] }[/math] is the position of one of the [math]\displaystyle{ N }[/math] heap items in [math]\displaystyle{ TheHeap }[/math]. As long as this heap item is stored, [math]\displaystyle{ i }[/math] is permanently associated with this heap item (and can hence be used to locate and access this heap item at any time). The correspondence between the heap items and these numbers [math]\displaystyle{ i }[/math] is one-to-one.
    2. [math]\displaystyle{ TheHeap[Positions[i]].ID=i }[/math].
  7. Heap property: For each [math]\displaystyle{ i\in\{2,...,N\} }[/math], it is [math]\displaystyle{ TheHeap[i].key\ge TheHeap[\lfloor i/2 \rfloor ].key. }[/math].