# Min heap and max heap implementation in Python

## What is min-heap and max-heap

A heap is a data structure based on binary tree. It's designed to efficiently access the smallest or largest element in a collection of items. It follows properties of a complete binary tree. So, it's also known as binary heap.

A min-heap(max-heap) is a binary tree such that

- The data in each node is less(greater) than or equal to the data in node's children.
- The binary tree is complete. A complete binary tree means all levels are completely filled except the last level and the last level has all nodes as left as possible.

## How is binary heap represented

A binary heap is typically represented as an array.

- The root node is arr[0]
- The parent node for the ith node is arr[(i-1)/2]
- the left child node for the ith node is arr[2*i+1]
- the right child node for the ith node is arr[2*i+2]

Level order traversal is used to achieve the array representation.

Example:

```
binary tree:
6(0)
/ \
4(1) 8(2)
/ \ /
2(3) 9(4) 7(5)
array: [6,4,8,2,9,7]
```

## Application of heap

The heap is broadly used to solve the following problems. We will learn more in future posts. Here we will be focus on the heap implementation.

- Heap sort in O(nlogn) time
- Priority queue
- Graph algorithms
- Many other problems

## What is heapify

Heapify is the process to build the heap data structure using binary tree.

We start the process from the first index of non-leaf node.

```
6 6 6 2 2
/ \ / \ / \ / \ / \
4 8 --> 4 7 --> 2 7 --> 6 7 --> 4 7
/ \ / / \ / / \ / / \ / / \ /
2 9 7 2 9 8 4 9 8 4 9 8 6 9 8
```

## Implementaion

```
def left_child(mylist, k):
return 2 * k + 1
def right_child(mylist, k):
return 2 * k + 2
def is_leaf(mylist, k):
return 2 * k >= len(mylist)
def heapify(mylist, k):
if is_leaf(mylist, k):
return
n = len(mylist)
# get left and right child index
left = left_child(mylist, k)
right = right_child(mylist, k)
# find the smallest elements among current node, left and right child
smallest = k
if left < n and mylist[k] > mylist[left]:
smallest = left
if right < n and mylist[smallest] > mylist[right]:
smallest = right
# swap current node and the smallest child
if smallest != k:
mylist[k], mylist[smallest] = mylist[smallest], mylist[k]
heapify(mylist, smallest)
def build_min_heap(mylist):
n = len(mylist) // 2 - 1
for i in range(n, -1, -1):
heapify(mylist, i)
def parent(k):
return (k - 1) // 2
def insert(mylist, val):
mylist.append(val)
k = len(mylist) - 1
while k > 0 and mylist[k] < mylist[parent(k)]:
mylist[k], mylist[parent(k)] = mylist[parent(k)], mylist[k]
k = parent(k)
def remove(mylist):
min = mylist[0]
mylist[0] = mylist[len(mylist) - 1]
mylist.pop(len(mylist) - 1)
heapify(mylist, 0)
return min
def print_heap(mylist):
for i in range(len(mylist) // 2):
left = 2 * i + 1
right = 2 * i + 2
if left < len(mylist) and right < len(mylist):
print(
f"parent: {mylist[i]} left-child: {mylist[left]} right-child: {mylist[right]}"
)
elif left < len(mylist):
print(f"parent: {mylist[i]} left-child: {mylist[left]} right-child: None")
test_list = []
insert(test_list, 6)
insert(test_list, 4)
insert(test_list, 8)
insert(test_list, 2)
insert(test_list, 9)
insert(test_list, 7)
print(test_list)
print_heap(test_list)
test_list_1 = [6, 4, 8, 2, 9, 7]
build_min_heap(test_list_1)
print(test_list_1)
print_heap(test_list_1)
remove(test_list_1)
print(test_list_1)
print_heap(test_list_1)
```