Min and max heaps in Python3
12-17-2017
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.