Heap as array

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]N_\text{max}\in\mathbb{N}[/math], which is constant throughout the object's lifetime.
   2. a current number of items [math]N\in\mathbb{N}_{0}[/math], which is dynamically changing, but it is [math]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]key[/math] of type [math]\mathcal{K}[/math]
   2. a component named [math]ID[/math], which is a natural number and ranges from [math]1,...,N_\text{max}[/math].
3. There is an array [math]TheHeap[/math] with index range [math]1,...,N_\text{max}[/math] and component type heap item. The currently stored items are [math]TheHeap[1],...,TheHeap[N][/math].
4. There is an index handler [math]IH[/math] with maximum size [math]N_\text{max}[/math] and value type [math]\{1,\ldots,N_\text{max}\}[/math]. For each used index [math]i\in\{1,...,N_\text{max}\}[/math], the associated value is the position of one of the [math]N[/math] heap items in [math]TheHeap[/math]. As long as this heap item is stored, [math]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]i[/math] is one-to-one.
5. Heap property: For each [math]i\in\{2,...,N\}[/math], it is [math]TheHeap[i].key\ge TheHeap[\lfloor i/2 \rfloor ].key.[/math].

The heap property may be viewed as follows: Imagine a binary tree of [math]N[/math] nodes such that each height level except for the last one is full, and the last one is filled from left to right. The nodes have pairwise different indexes from [math]\{ 1,...,N \}[/math]:

1. The root is indexed [math]1[/math].
2. For a node with [math]i[/math], the left child (if existing) has index [math]2*i[/math], and the right child (if existing) has index [math]2*i+1[/math].

Now associate the node with index [math]i[/math] with the key [math]TheHeap[i].key[/math]. Then the heap property says that the key of a node is not larger than the keys of its children. In this case, we say that i fulfills the heap property.

In particular, the minimum key is associated with the root.

Remark

The implementations of the methods Bounded priority queue: number and Bounded priority queue: find minimum are trivial and, hence, left out here.