Heap Data Structure in Python | Min Head and Max Heap

Min and Max Heap Image Source: GFG

Heaps are Binary-tree-based data structures. The biggest advantage of the heap is we can access the minimum or maximum value in O(1) operation. The root node of the tree always will be the smallest (min-heap) or biggest (max-heap).

Heap Operations and Time Complexity

1. Get min/max value -> O(1)
2. Push -> O(logN)
3. Pop -> O(logN)
4. Searching -> O(N)
5. Heapify -> O(N)

There are mainly two types of Heaps : — Max Heap and Max Heap

1. Max Heap

In the max heap, every root node has a value greater than or equal to its children, we use an array in which arr[ r ] ≥ arr[ 2*r + 1 ] and arr[ r ] ≥ arr[ 2*r + 2 ], where r is the index of the node value in the array. See the below image.

50 ≥ 40 and 50 ≥ 37 which is same for any element i, arr[i] ≥ arr[2 * i + 1] and arr[i] ≥ arr[2 * i + 2].

Min-Heap

In the min-heap, every root node has a value less than or equal to its children, we use an array in which arr[ r ] ≤ arr[ 2*r + 1 ] and arr[ r ] ≤ arr[ 2*r + 2 ], where r is the index of the node value in the array. See the below image.

Python has a built-in min heap module which you can import using the following command.

import heapq

Create Min-Heap

Let's create an array and convert it into a Min Heap data structure.

import heapq

hq = [5,7, 9, 8, 3, 2]           # Array to convert into min heap
heapq.heapify(hq)                # Convert the array into a heap
print(hq)

#Output
[2, 3, 5, 8, 7, 9]               # Min heap

Pop, and replace the smallest value in the heap

First, let’s see the command to pop an element from the heap.

import heapq

hq = [5,7, 9, 8, 3, 2]           # Array to convert into min heap
heapq.heapify(hq)                # Convert the array into a heap
smallest_val = heap.heappop(hq)  # Method to pop the element
print(smallest_val)
print(hq)

#Output
2                  # smallest value
[3, 5, 8, 7, 9]    # Min heap

Now let’s pop the smallest value and add a new value simultaneously.

import heapq

hq = [5,7, 9, 8, 3, 2]            # Array to convert into min heap
heapq.heapify(hq)                 # Convert the array into a heap
val = heapq.heapreplace(hq, 4)    # Pop the smallest value and add new
print(val)
print(hq)

#Output
2
[3, 4, 5, 8, 7, 9]

Create Max-Heap

If you want to create a max heap out of an array, you must pass the values as negative values. The bigger value with negative values will become the smallest value that you can pop as absolute and your max heap is ready.

Let's implement it …

from heapq import heappop, heappush

def max_heap(li):
  h = []                            # An empty list for heap insert
  for i in li:                      # Insert the value as negative
    heappush(h, -i)
  
  #pop the values as absolute and return
  return [abs( heappop(h) ) for _ in range(len(h))]

#Call the function
if __name__ == "__main__":
  hq = [5,7, 9, 8, 3, 2]
  data = max_heap(hq)
  print(data)

#Output
[9, 8, 7, 5, 3, 2]

In summary, heap data structures, whether in the form of min-heaps or max-heaps, offer efficient ways to maintain priority-based order in a collection of elements. With operations like heapify, heappop, heapreplace, and heappush, they become valuable tools for tasks like sorting, scheduling, and more. By understanding the principles of heap management, developers can optimize their algorithms and improve the efficiency of various applications.