Min heap is a complete binary tree. A complete binary tree is a binary tree in which all levels are completely filled and all the nodes in the last level are as left as possible. Min heap should also meets this criteria: the parent’s key is less than both children’s keys. The smallest value is at the root.

Since it is complete (no holes in the tree),  it can be represented as an array. Each node’s position in the tree is corresponding to the index in the array.

The relationship between nodes has the formulas:

parentPos = (pos-1)/2
left = 2*pos+1
right=2*pos+2

This post is min heap implementation. The max heap is opposite order.

Part 1 – Max heap implementation
Part 2 – Min heap implementation
Part 3 – Priority queue implementation with heap

### Insert

We declare three attributes: heap, length and maxSize. heap is an array. maxSize is the max length of the array. It is used to initialize the array. length is actual number of elements in the array. It starts from 0.

To insert a new element, we put the new value at the end of the array. Then we move it up based on its value compared to its parent. If it’s value less than its parent, it should be switched the position with its parent, until it is below a smaller node and above a larger one. We call this process heap up (or trickle up).

## Python

### Remove

The remove operation is to remove the element with the smallest value, which is the first one in the array. When we remove the first element in the array, we move the last element to the first to fill out the empty spot. But this element’s value might be larger than its children’s. To correct this, we compare its value with its children’s values, and switch with the child with the smaller value, until it is below a smaller node and above a larger one. This process is called heap down (or trickle down). Heap down is more complicated than heap up because it has two children to compare.

## Python

### Search

Since the underlying data structure is an array, we iterate through all elements to find the one matched with the key.

Please refer to search in max heap for implementation.

### Traversal

The traversal is to visit all nodes in the heap. The same as binary tree, it has inorder, preorder, postorder and level order traversal.

Inorder is to traverse the left subtree, visit the root, traverse the right subtree.

Preorder is to visit the root, traverse the left subtree, traverse the right subtree.

Postorder is to traverse the left subtree, traverse the right subtree, visit the root.

Level order is to traverse the nodes level by level.

please refer to the traversal of max heap for the implementation.