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.
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.
This adds a new item to the heap.
This removes the min or max item.
This returns the root item.
Exchanges two items.
Moves item up to its proper position in the heap.
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 =  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 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.