# Heaps

The word *heap* is used in a couple of different context in Computer Science. A heap is sometimes refers to an area in the memory which is used for dynamic memory allocation. Another meaning, and the topic of this article, is a data structure which is very useful and important.

Famous search algorithms like Dijkstra’s algorithm^{1} and some reinforcement learning techniques like Hidden Markov Model (HMM)^{2} which is especially known for its application in pattern recognition (speech, handwriting, gesture recognition) uses the heap.

## What is a Heap?

A heap is a special Tree-based data structure in which the tree is a *complete* Binary Tree in which each level has all of its nodes. The exception to this is the bottom level of the tree, which we fill in from left to right.

It is called;

**Min Heap**, if each parent node is*less than or equal to*its child node**Max Heap**, if each parent node is*greater than or equal to*its child node

The heap above is called a **Min Heap** since, each value of nodes is less than or equal to the value of child nodes.

## Representation

We can represent a heap as an array like this;

- Root node,
*i = 0*is the first item of the array - A parent node,
*parent(i) = (i-1) / 2* - A left child node,
*left(i) = 2i + 1* - A right child node,
*right(i) = 2i + 2*

For example,

- Parent node of
**33**is,*parent(7) = (7-1) / 2 = 3*so,*i = 3*is**14** - Left child node of
**11**is,*left(2) = (2 x 2) + 1 = 5*so,*i = 5*is**19** - Right child node of
**14**is,*right(3) = (2 x 3) + 2 = 8*so,*i = 8*is**17**

## Implementation

We need to implement two different methods in order to build a heap from an array. These methods are `min_heapify()`

to make some node and its descendant nodes meet the min heap property and `build_min_heap()`

to produce a heap from an arbitrary array.

We can build a min heap by applying `min_heapify()`

repeatedly.

`min_heapify()`

and `build_min_heap()`

```
def get_left_child(i):
return 2 * i + 1
def get_right_child(i):
return 2 * i + 2
def min_heapify(arr, i):
left = get_left_child(i)
right = get_right_child(i)
smallest = i
if left < len(arr) and arr[i] > arr[left]:
smallest = left
if right < len(arr) and arr[smallest] > arr[right]:
smallest = right
if smallest != i:
arr[i], arr[smallest] = arr[smallest], arr[i]
min_heapify(arr, smallest)
```

and now we can repeatedly call `min_heapify()`

function in order to build a **Min Heap**.

```
def build_min_heap(arr):
for i in reversed(range(len(arr)//2)):
min_heapify(arr, i)
```

`max_heapify()`

and `build_max_heap()`

```
def max_heapify(arr, i):
left = get_left_child(i)
right = get_right_child(i)
largest = i
if left < len(arr) and arr[left] > arr[largest]:
largest = left
if right < len(arr) and arr[right] > arr[largest]:
largest = right
if largest != i:
arr[i], arr[largest] = arr[largest], arr[i]
max_heapify(arr, largest)
```

and now we can repeatedly call `max_heapify()`

function in order to build a **Max Heap**.

```
def build_max_heap(arr):
for i in reversed(range(len(arr)//2)):
max_heapify(arr, i)
```

## Time Complexity

*Average* and *Worst Case* time complexites of the heap data structure is as follows.

Operation | Average | Worst Case |
---|---|---|

Search | O(n) | O(n) |

Insert | O(1) | O(log n) |

Delete | O(log n) | O(log n) |

Peek | O(1) | O(1) |

## References

- Wikipedia,
*Dijkstra’s algorithm* - Wikipedia,
*Hidden Markov Model*