Making a heap

So what is a heap.

I’ll help jog your memory, in simple terms that we should understand, it’s a tree that preserve the heap invariablity, which means (for a min heap), every parent node is smaller (or equal) to their children node.

flowchart TB
  A[1] --> B[3]
  A --> C[6]
  B --> D[5]
  B --> E[9]
  C --> F[8]

You can notice that it is a Binary tree, there is no special rule but the invariablity, every parent is ≤ than their children. This ensure that

1. The root node is always the min value of the heap
2. Nodes can be quickly re-arrange to maintain heap property in case edit (addition/ removal is made)

A heap is often used as Priority Queue, which is used in many cases like scheduling, prority keeping, … where keeping a quick track of the top (min) values are important as elements are added and removed.

Now how do we build this tree?

The idea is now clear

1. We need a tree structure
2. We need to keep the invariablity

I’ll explain the tree structure in a bit more detail in next section. For the Invariablity, the solution is rather simple.
We “re-arrange” the tree with heapify Up, or Down every time a node is added, this is the core operation of the heap that keeps the min heap stable. This is simply saying, when adding or remove a node, bubble the node up (or down) and swap it with it’s parent (or children) until it’s in the correct place that keeps the heap correct.

A simple example is imagine we add a ‘3’ to that heap, at the start, in the right most children, we would afterwards do a heap up and swap this node with it’s children, what would the final result look like?

Something like this.

flowchart TB
  A[1] --> B[3]
  A --> C[3]
  B --> D[5]
  B --> E[9]
  C --> F[8]
  C --> G[6]

The ‘3’ at the start is the right most child, was swapped with it’s parent ‘6’ to keep the heap correct.

The tree

Mentally, we keep the heap concept as a tree, but in implementation, a heap is mostly implemented as an expanding array where the array itself represents a tree.
With arr[0] is the root, a[1] is left and a[2] the right. a[3] is the left most, then so on till a[6] the right most node.

flowchart TB
  A[a0] --> B[a1]
  A --> C[a2]
  B --> D[a3]
  B --> E[a4]
  C --> F[a5]
  C --> G[a6]

When we buid the array this way, we keep filling the array/tree based on the next missing child node, this have the advantage of keeping the array not too sparse (balanced tree) which saves space, and at the same time, this deterministic indexing/odering allow us to quickly jump to a node’s parent or child without keeping any extra references beside the node’s index itself.

Let’s quickly whip up the tree’s scaffolding, starting with a self managed array with capacity and extend method to be used when we run out of space

class Heap:
	def __init__(self):
		self.cap = 2 ** 3
		self.heap = [None] * self.cap
		self.len = 0
 
	# double heap size
	def full(self):
		return self.len >= self.cap
 
	def extend(self):
		newHeap = [None] * (self.cap * 2)
		for i, val in enumerate(self.heap):
			newHeap[i] = val
		self.cap = self.cap * 2
		self.heap = newHeap
 

He also have some array helper methods here

	def empty(self): return self.len == 0
	def outBound(self, i): return i >= self.len
 
	def lastIndex(self):
		if self.empty(): raise Exception()
		return self.len - 1
	def nextIndex(self):
		# what's the index for adding to the heap
		return self.len
 
	def set(self, i, val):
		if self.outBound(i): raise Exception()
		self.heap[i] = val
	def get(self, i):
		if self.outBound(i): raise Exception()
		return self.heap[i]
 
	# swap value of two nodes
	def swap(self, i, j):
		tempVal = self.get(j)
		self.set(j, self.get(i))
		self.set(i, tempVal)

Then we need the some “tree” traversal methods to help us traverse this mental tree

	def left(self,n):
		return n * 2 + 1
	def right(self,n):
		return (n+1) * 2
	def parent(self,n):
		return (n-1) // 2

That would be enough for us to traverse the tree with ease, now let’s move on to the heap itself.

The heap

For implementing the heap, there are just two operation that it needs to do:

• Push (inserting a node)
• Pop (pop the root)
  Note here that we would insert a new node at the end and do a heapUp and when poping, we’re removing the root, replace it with the last node in the heap, then doing a heapDown.

Keeping in mind that heap up basically means, going up and swap current node until correct (and vice versa for down), here is the implementation of the core ops

	def push(self, val):
		if self.full(): self.extend()
 
		# add node at the end
		nextIndex = self.nextIndex()
		self.len += 1
		self.set(nextIndex, val)
 
		# now that node's added, keep the heap correct
		self.heapUp(start=nextIndex)
 
	def pop(self, val):
		self.swap(0, self.lastIndex())
		self.len -= 1
 
		# no need to clear the value of the last index cause we already decrease the len (will err if read)
 
		self.heapDown(start=0)

That’s most of the mental logic of a heap, there’s only the heap up and down left. If you already mentaly understand the idea and don’t want the implementation details, feel free to skip the code.
The heap down logic is a bit more complex than the up one, simply due to the fact that we have two children and have to make correct swaping choice, compared to just checking the parent in the heap up. For a one line explanation:

• Heap up: while parent is in wrong place (node smaller than parent), swap node with parent
• Heap down: while node is in wrong place (node larger than either of child), swap node with smaller of the two (to ensure after swap node is smaller than both)

	def heapUp(self, start):
		node = start
		while True:
			parent = self.parent(node)
 
			# hit root then done
			if parent == node: return
 
			# correct position
			if self.get(parent) <= self.get(node): return
 
			self.swap(node,parent)
			node = parent # continue going up
 
	def heapDown(self, start):
		node = start
		while True:
			left = self.left(node)
			# have no children, done
			if self.outBound(left): return
 
			right = self.right(node)
			minChild = left
			if not self.outBound(right) and self.get(right) < self.get(left):
				minChild = right
 
			# if correct, done
			if self.get(node) < self.get(minChild): return
 
			self.swap(node, minChild)
			node = minChild # continue downwards

Hey you made it to the end, congratulations 🥳. Was it confusing to understand? I hope not. I hope that my code was some what clean so that the concept of tree-array implementation, traversal, and heapify up/down is simple to understand. Hope this helped. Cheers 🧀