A heap is a data structure that supports the operations *insert* and
*extract*. Heaps typically come in two varieties, *min heap* (for extracting the
minimum value) and *max heap*. A heap is built using a binary tree where each
node is said to *dominate* the nodes below it. The meaning of dominate depends
on the type of heap being implemented, for a *min heap* the key of each node is
*less* than the keys of both of child nodes.

From here on, without loss of generality, we will talk about a heap of integers
(keys) ignoring satellite data that may or may not be associated with each
integer key. *Node* and *key* will therefore be used interchangeably.

Like a binary search tree a heap can be implemented using a linked data structure. There is however, a nifty method of implementing a heap using an array, thereby reducing the memory requirements since there are no pointers to store. We store the data as an array of keys and use the index of the keys to implicitly satisfy the role of pointers.

**The root node is stored at index 1 and all operations are 1-indexed**.

For node at index *k* the left child can be found at index *2k* and the
right child at index *2k + 1*. (Quite clearly, checks must be made prior to
access that an index lies within the underlying array).

One additional limitation must be placed on the tree, that it is *complete*, i.e
all levels of the tree are full with the possible exception of the last level,
and if the last level is not full all nodes are as far to the left as
possible. This limitation results in an array with no holes in it.

A heap as just described may be defined in Go as such;

```
type heap struct {
xs []int
}
```

We wrap the array inside a struct to abstract the implementation and limit access to the functions that we define. Care must be taken to remember that the heap is 1-indexed.

```
func (h *heap) Len() int {
return len(h.xs) - 1 // heap is 1-indexed
}
```

Insertion of a key into a heap can be achieved by adding the key to the end of
the underlying array. Whilst maintaining the structure of the heap this may
violate the *heap property* of the parent of the newly inserted key, namely the
parent of the newly inserted key may not be dominant. The heap property for the
parent node can be restored by swapping the newly inserted child node with the
parent. This may in turn, result in the parent above violating the heap
property. We can continue this *bubbling* of a node to successively higher nodes
until the heap property is restored. When swapping a node with the parent node
we need not consider the sibling node since if a node dominates the parent then
by definition it dominates the other sibling also.

```
// Insert x into the heap
func (h *heap) Insert(x int) {
(*h).xs = append(h.xs, x)
h.bubbleUp(len(h.xs) - 1)
}
```

Note that parenthesis are required to dereference the heap pointer in order to save the
return value of `append()`

.

```
func (h *heap) bubbleUp(k int) {
p, ok := parent(k)
if !ok {
return // k is root node
}
if h.xs[p] > h.xs[k] {
h.xs[k], h.xs[p] = h.xs[p], h.xs[k]
h.bubbleUp(p)
}
}
```

The function terminates when either the node is in place or it has reached the root position.

We define functions for manipulating indices as described above;

```
// get index of parent of node at index k
func parent(k int) (int, bool) {
if k == 1 {
return 0, false
}
return k / 2, true
}
// get index of left child of node at index k
func left(k int) int {
return 2 * k
}
// get index of right child of node at index k
func right(k int) int {
return 2*k + 1
}
```

We are now ready to extract the key for which our heap was designed (minimum
or maximum). This key is clearly at index 1, extracting this key however, leaves a hole which
must be filled. Swapping the last key of the array into the hole restores the
heap structure but once again may violate the *heap property*. In a similar
fashion to insertion we can restore the heap property by bubbling this node down
the tree until it is either a leaf node or no longer violates the heap
property. In doing this we must consider both child nodes and swap any
non-dominant parent node with the child node that is *most* dominant in order for
the heap property of these three nodes to be maintained.

```
// ExtractMin: get minimum value of heap
// and remove value from heap
func (h *heap) ExtractMin() (int, bool) {
if h.Len() == 0 {
return 0, false
}
v := h.xs[1]
h.xs[1] = h.xs[h.Len()]
(*h).xs = h.xs[:h.Len()]
h.bubbleDown(1)
return v, true
}
func (h *heap) bubbleDown(k int) {
min := k
c := left(k)
// find index of minimum value (k, k's left child, k's right child)
for i := 0; i < 2; i++ {
if (c + i) <= h.Len() {
if h.xs[min] > h.xs[c+i] {
min = c + i
}
}
}
if min != k {
h.xs[k], h.xs[min] = h.xs[min], h.xs[k]
h.bubbleDown(min)
}
}
```

Caution is again needed here since the array indexing and loop conditionals are unusual because of the 1-indexing.

See Github for complete source code and tests.

### Final Note

This implementation is based on the text *The Algorithm Design
Manual* [Ski08]. In this, the author Steven S. Skiena makes an interesting
observation on the construction of a heap. At first glance one may think to
construct a heap by repeated calls to `insert()`

. Inserting into a heap (like
any balanced tree) takes O(log *n*)), so heap construction in this manner has
worst case running time of O(*n* log *n*). We can do better, Skiena notes, if we
observe that a *full*, *complete* tree of *n* nodes has *n/2* leaf nodes. These
leaf nodes may be considered as sub-trees that maintain the heap property (since
they have only a single node). If then, we base a heap on any array we need only
*bubble up* *n/2* nodes in order to achieve a heap for which the heap property
holds. This still gives an *upper bound* of O(*n* log *n*), however Skiena goes
on to show that this leads to a *not quite geometric* series that he then
assures us quickly converges to linear. He does however, caution us that this
benefit may not be that useful if the algorithm we plan to use our heap for is
not governed by the construction (i.e heapsort will still run in O(*n* log
*n*)).

#### Bibliography:

[Ski08] - **The Algorithm Design Manual**, Steven S. Skiena