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)
``````