Heap in Python: Min & Max Heap Implementation (with code)

Python is versatile with a wide range of data structures. One such is the heap. While they are not as commonly used, they can be incredibly useful in certain scenarios. In this article, we will learn what a heap is in Python. We will also understand how to implement max heap and min heap concepts and the difference between them. So, let's get started!

What is Heap in Python?

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

As we all know, the complete binary tree is a tree with every level filled and all the nodes are as far left as possible. In the binary tree, it is possible that the last level is empty and not filled. Now, you must be wondering what is the heap property.

In the heap data structure, we assign key-value or weight to every node of the tree. Now, the root node key value is compared with the children’s nodes and then the tree is arranged accordingly into two categories i.e., max-heap and min-heap.

The heap data structure is basically used as a heapsort algorithm to sort the elements in an array or a list. These algorithms can be used in priority queues, order statistics, Prim's algorithm or Dijkstra's algorithm, etc.

As learned earlier, there are two categories of heap data structure i.e. max-heap and min-heap. Let us understand them below but before that, we will study the heapify property to understand max-heap and min-heap. 

What is the use of a heap? 

Python uses the heap data structure as it is a highly efficient method of storing a collection of ordered elements. It is useful for keeping track of the largest and smallest elements in a collection, which is a common task in many algorithms and data structures. Priority queues, which are commonly used in task scheduling and network routing, are also implemented using the heap.

How to create a heap in Python?

You can create a heap data structure in Python using the heapq module. To create a heap, you can start by creating an empty list and then use the heappush function to add elements to the heap.

Example:

import heapq
new_heap = []
heapq.heappush(new_heap, 2)
heapq.heappush(new_heap, 3)
heapq.heappush(new_heap, 7)
heapq.heappush(new_heap, 9)
print(new_heap)

Output

[2, 3, 7, 9]

According to Official Python Docs, this module provides an implementation of the heap queue algorithm, also known as the priority queue algorithm.

What is Heapify?

The process of creating a heap data structure using the binary tree is called Heapify. The heapify process is used to create the Max-Heap or the Min-Heap. Let us study the Heapify using an example below:

Consider the input array as shown in the figure below:

Using this array, we will create the complete binary tree:

We will start the process of heapify from the first index of the non-leaf node as shown below:

Now we will set the current element “k” as “largest” and as we know the index of a left child is given by “2k + 1” and the right child is given by “2k + 2”.

Therefore, if the left child is larger than the current element i.e. kth index we will set the “largest” with the left child’s index, and if the right child is larger than the current element i.e., kth index then we will set the “largest” with right child’s index.

Lastly, we will swap the “largest” element with the current element(kth element).

We’ll repeat the above steps 3-6 until the tree is heaped.

Here is the algorithm for Max Heapify:

maxHeapify(array, size, k)
  set k as largest
  leftChild = 2k + 1
  rightChild = 2k + 2
  
  if leftChild > array[largest]
    set leftChildIndex as largest
  if rightChild > array[largest]
    set rightChildIndex as largest

  swap array[k] and array[largest]

Here is the algorithm for Min Heapify:

minHeapify(array, size, k)
  set k as smallest
  leftChild = 2k + 1
  rightChild = 2k + 2
  
  if leftChild < array[smallest]
    set leftChildIndex as smallest
  if rightChild < array[smallest]
    set rightChildIndex as smallest

  swap array[k] and array[smallest]

What is Max Heap?

When the value of each internal node is larger than or equal to the value of its children node then it is called the Max-Heap Property. Also, in a max-heap, the value of the root node is largest among all the other nodes of the tree. Therefore, if “a” has a child node “b” then:

Key(a) >= key(b)

represents the Max-Heap Property. Let us display the max-heap using an array. Therefore, the root node will be arr[0]. So, for kth node i.e., arr[k]:

arr[(k - 1)/2] will return the parent node

arr[(2*k) + 1] will return left child

arr[(2*k) + 2] will return right child

Algorithm for Max Heap:

MaxHeap(array, size)
  loop from the first index down to zero
    call maxHeapify

Algorithm for Insertion in Max Heap:

If there is no node, 
  create a new Node.
else (a node is already present)
  insert the new Node at the end 
  
maxHeapify the array

Algorithm for Deletion in Max Heap:

If nodeDeleted is the leaf Node
  remove the node
Else swap nodeDeleted with the lastNode
  remove nodeDeleted
   
maxHeapify the array

Max Heap Implementation

Here is the Python implementation with full code for Max Heap:

def max_heapify(A,k):
    l = left(k)
    r = right(k)
    if l < len(A) and A[l] > A[k]:
        largest = l
    else:
        largest = k
    if r < len(A) and A[r] > A[largest]:
        largest = r
    if largest != k:
        A[k], A[largest] = A[largest], A[k]
        max_heapify(A, largest)

def left(k):
    return 2 * k + 1

def right(i):
    return 2 * k + 2

def build_max_heap(A):
    n = int((len(A)//2)-1)
    for k in range(n, -1, -1):
        max_heapify(A,k)

A = [3,9,2,1,4,5]
build_max_heap(A)
print(A)

Output:

[9, 4, 5, 1, 3, 2]

What is Min Heap?

When the value of each internal node is smaller than the value of its children node then it is called the Min-Heap Property. Also, in the min-heap, the value of the root node is the smallest among all the other nodes of the tree. Therefore, if “a” has a child node “b” then:

Key(a) < key(b)

represents the Min Heap Property. Let us display the max heap using an array. Therefore, the root node will be arr[0]. So, for kth node i.e., arr[k]:

arr[(k - 1)/2] will return the parent node

arr[(2*k) + 1] will return left child

arr[(2*k) + 2] will return right child

Algorithm for Min Heap:

MinHeap(array, size)
  loop from the first index down to zero
    call minHeapify 

Algorithm for Insertion in Min Heap:

If there is no node, 
  create a new Node.
else (a node is already present)
  insert the new Node at the end 
  
minHeapify the array

Algorithm for Deletion in Min Heap:

If nodeDeleted is the leaf Node
  remove the node
Else swap nodeDeleted with the lastNode
  remove nodeDeleted
   
minHeapify the array

Min Heap Implementation

Here is the Python implementation with full code for Min Heap:

def min_heapify(A,k):
    l = left(k)
    r = right(k)
    if l < len(A) and A[l] < A[k]:
        smallest = l
    else:
        smallest = k
    if r < len(A) and A[r] < A[smallest]:
        smallest = r
    if smallest != k:
        A[k], A[smallest] = A[smallest], A[k]
        min_heapify(A, smallest)

def left(k):
    return 2 * k + 1

def right(k):
    return 2 * k + 2

def build_min_heap(A):
    n = int((len(A)//2)-1)
    for k in range(n, -1, -1):
        min_heapify(A,k)

A = [3,9,2,1,4,5]
build_min_heap(A)
print(A)

Output:

[1, 3, 2, 9, 4, 5]

Min Heap vs Max Heap 

Here are the key difference between Min and Max Heap in Python:

Time complexity

The running time complexity of the building heap is O(n log(n)) where each call for heapify costs O(log(n)) and the cost of building heap is O(n). Therefore, the overall time complexity will be O(n log(n)).

Applications of Heap

A heap is used for a variety of purposes. It is a powerful tool used in sorting, searching, and graph traversal algorithms, as well as other applications requiring efficient management of a collection of ordered elements. Following are some of the main practical applications of it:

• Heap is used while implementing a priority queue. It is another data structure to access and remove the item in the highest priority. 
• It is used in the Heap sort, selection algorithm, Prim’s algo, and Dijkstra's algorithm.
• We can use max-heap and min-heap in the operating system for the job scheduling algorithm.
• It is used in order statistics, for tasks like how to find the median of a list of numbers.

Conclusion

Overall, the Heap data structure in Python is very useful when it comes to working with graphs or trees. It helps us improve the efficiency of various programs and problem statements. You also know how to implement max heap and min heap with their algorithms and full code.