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

The heap property may be viewed as follows: Imagine a binary tree of $N$ 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 $\{1,...,N\}$:

1. The root is indexed $1$.
2. For a node with $i$, the left child (if existing) has index $2\ast i$, and the right child (if existing) has index $2\ast i+1$.

Now associate the node with index $i$ with the key $TheHeap[i].key$. 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.