A min and max heap is a binary heap which is a binary tree that is ordered in a specific way. In the min heap each node is greater than or equal to the value of its parent, with the minimum value element at its root. For the max-heap the opposite is true.

The heap data structure was invented by J. W. J. Williams in 1964, as a data structure for the heapsort sorting algorithm. He was a British born computer scientist that spent the latter part of his career in Ottawa, Canada. The heapsort algorithm divides it’s input into sorted and unsorted regions and it iteratively shrinks the unsorted region by extracting the largest element and moving that to the sorted region.

heapsort algorithm in action

Heaps are usually implemented in an array. In a one based array, (array keeping a zero as the first element) each node has a left child at index * 2 and a right child at index * 2 + 1. To get to the parent node, divide index by 2. To implement this data structure in python, we will create a class with the following functions.

Public functions

push(newItem)
This adds a new item to the heap.

pop()
This removes the min or max item.

peek()
This returns the root item.

Private functions

__swap(item1, item2)
Exchanges two items.

__floatUp()
Moves item up to its proper position in the heap.

__bubbleDown()
Moves item down to its proper position.

With these functions our implementation of a max heap looks like this. To get a min heap, all you have to do is reverse some of the inequality signs

              
  class MaxHeap:
    def __init__(self, items=[]):
      super().__init__()
      self.heap = [0]
      for i in items:
        self.heap.append(i)
        self.__floatUp(len(self.heap) - 1)

    def push(self, data):
      self.heap.append(data)
      self.__floatUp(len(self.heap) - 1)

    def peek(self):
      if len(self.heap) > 1:
        return self.heap[1]
      else:
        return False
        
    def pop(self):
      if len(self.heap) > 2:
        self.__swap(1, len(self.heap) - 1)
        max = self.heap.pop()
        self.__bubbleDown(1)
      elif len(self.heap) == 2:
        max = self.heap.pop()
      else: 
        max = False
      return max

    def __swap(self, i, j):
      self.heap[i], self.heap[j] = self.heap[j], self.heap[i]

    def __floatUp(self, index):
      parent = index//2
      if index <= 1:
        return
      elif self.heap[index] > self.heap[parent]:
        self.__swap(index, parent)
        self.__floatUp(parent)

    def __bubbleDown(self, index):
      left = index * 2
      right = index * 2 + 1
      largest = index
      if len(self.heap) > left and self.heap[largest] < self.heap[left]:
        largest = left
      if len(self.heap) > right and self.heap[largest] < self.heap[right]:
        largest = right
      if largest != index:
        self.__swap(index, largest)
        self.__bubbleDown(largest)
              
            

To practice this concept try solving a problem like the running mean using heaps.

Contact