View source for Heap as array

[[Category:Data Structure]]
==General information==
'''Abstract Data Structure:''' [[Bounded priority queue]]

'''Implementation Invariant:'''
# For each object of "Heap as array", there is
## a specific '''maximum number of items''' <math>N_\text{max}\in\mathbb{N}</math>, which is constant throughout the object's lifetime.
## 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.
# There is an internal type '''heap item''' with two components:
## a component named <math>key</math> of type <math>\mathcal{K}</math>
## a component named <math>ID</math>, which is a [[Numbers#natural numbers|natural number]] and ranges from <math>1,...,N_\text{max}</math>.
# 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>.
# There is an array <math>Positions</math> with index range <math>1,...,N_\text{max}</math> and integral components from <math>\{1,...,N_\text{max}\}</math>.
# There is an [[ordered sequence]] <math>Unused</math> of [[Numbers#natural numbers|natural numbers]], which has length <math>N_\text{max}-N</math> and stores pairwise different numbers from <math>\{1,...,N_\text{max}\}</math>.
# For each <math>i\in\{1,...,N_\text{max}\}</math> not in <math>Unused</math>:
## <math>Positions[i]</math> 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.
## <math>TheHeap[Positions[i]].ID=i</math>.
# '''Heap property:''' For each <math>i\in\{2,...,N\}</math>, it is <math>TheHeap[i].key\ge TheHeap[\lfloor i/2 \rfloor ].key.</math>.
In summary, <math>Positions</math> stores the positions of all heap items, <math>Unused</math> stores all currently unused indexes of <math>Positions</math>, and the ID of each heap item refers back to its corresponding index in <math>Positions</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>:
# The root is indexed <math>1</math>.
# 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|Bounded priority queue: number]] and [[Bounded priority queue|Bounded priority queue: find minimum]] are trivial and, hence, left out here.

==References==