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)