A binary heap is a data structure where the topmost element is either the smallest or the largest. It’s useful in cases where you need to keep track of some sort of order or even sort elements as in the sorting algorithm variant. I like to think of them as a binary tree where, in the case of a min heap, the root node is the smallest element in entire tree, and in the case of a max heap, it’s the largest element in the entire tree. This is also going to be in Python, which as of python 3.10+ has max heap support via heapify_max()
By default, I’ll be referring to a minheap when I mention a heap, and will explicitly mention the max heap. I’m also going to be keeping the tree balanced in most cases by assuming they are complete binary trees. That gives us a better chance at getting optimal performance of log(n). If the tree is skewed heavily towards either side, that degenerates to O(N) time complexity.
We rely on the heap property which is basically that, for every node i with parent p , the key in p is smaller or equal to the key in i. It’s important to note that a heap is not globally ordered per se, but partially ordered. At each level, neither child is guaranteed to be sorted with respect to the other.
In the image below, the first tree is a minheap, and as you can see 6 is the least element in the tree, while in the second tree, 17 is the largest element in the tree.
You can represent a heap using its level order traversal in an array. For the ith element in an array, you can access the children as:
left_child = 2*i + 1
right_child = 2*i + 2
Inversely, you can access the parent node of a specific child by doing the reverse of the above for some child node i. We want to take the floor because for the right child, (i-1)/2 would not give you an integer for some even i.
parent_node = (i-1)//2
A heap supports the typical operations of a data structure such as being able to insert, delete(from a specific point), find nodes and being able to build it from a list. To insert to the heap, we want to do it at the end of the heap. This is fairly easy, but unfortunately it might violate the heap property if the value to be inserted is larger than the parent( and that might be the case for the parent’s parent). So we somehow need to maintain this property by recursively comparing it with the parent. This is often called percolating up.
In the worst case, we might need to keep doing it until we get to the root of the tree so in the worst case, the time complexity for doing an insert is bounded by the height of the tree. Since we assumed it’s a complete balanced binary tree, that’s approximately log(n). Technically there’s some constant just before it but we can ignore it.
def insert(heap, value):
heap.append(value)
i = len(heap) - 1
# Percolate up
while i > 0:
parent = (i - 1) // 2
if heap[parent] <= heap[i]:
break # Heap property satisfied
heap[parent], heap[i] = heap[i], heap[parent]
i = parent
For deletion operations, we need to pop the root which is the only interface to do it. We also need to maintain the heap order, so ensuring that whatever value we replace as the root maintains the heap order. To do so, we need to percolate down We can replace the last element as the root, and then, we can ensure this new root maintains the heap order. So we need to swap the root with the smaller child and recursively do it until we get to some leaf node. Ends up again being about log(N).
def pop_min(heap):
if not heap:
return None
min_val = heap[0]
heap[0] = heap[-1]
heap.pop()
# Percolate down
i = 0
while True:
left = 2*i + 1
right = 2*i + 2
smallest = i
if left < len(heap) and heap[left] < heap[smallest]:
smallest = left
if right < len(heap) and heap[right] < heap[smallest]:
smallest = right
if smallest == i:
break # Heap property satisfied
heap[i], heap[smallest] = heap[smallest], heap[i]
i = smallest
return min_val
We can build a heap in two ways. Inserting the elements one at a time or using the entire list. If you insert using proper heap operations, the cost is O(n log n). If you insert into a sorted list, the cost is O(n²). Heapify is O(n), which is even better. We can find the place to insert it at using binary search so log(n) but inserting in the middle of a python list is actually O(n) because you have to shift the elements over. If you are inserting n items, the cumulative cost is O(n)² .
The other approach is to build the heap directly from the list itself. Python exposes a heapify() api that makes this trivial and has a time complexity of O(n). The gist of how it works is that, since a binary heap, is a complete tree, most of the nodes are at the bottom or close to it, so the actual cost to sift down is very cheap, maybe 0 or 1. We start by identifying the last parent node using the formula above. We assume the leaf nodes are valid heaps since they have no child nodes. In fact, while the math can get a bit complicated the code is relatively straightforward. It’s some variations of this:
def heapify(arr):
n = len(arr)
# Start from last parent node
for i in reversed(range(n // 2)):
sift_down(arr, i, n)
# For an input like n=6, we would go to nodes 2, 1, 0
Using Python’s heapq module:
import heapq
# Create a min heap from a list
heap = [3, 1, 4, 1, 5, 9, 2, 6]
heapq.heapify(heap) # O(n) - in-place transformation
# Insert an element
heapq.heappush(heap, 0) # O(log n)
# Pop the minimum element
min_val = heapq.heappop(heap) # O(log n)
# Push then pop (more efficient than separate calls)
val = heapq.heappushpop(heap, 7) # O(log n)
# Pop then push
val = heapq.heapreplace(heap, 8) # O(log n)
For max heaps in python versions less than 3.10, since heapq supports min heaps natively, you can negate values:
# Max heap simulation using min heap
max_heap = [-x for x in [3, 1, 4, 1, 5]]
heapq.heapify(max_heap)
# Get max (negate back)
max_val = -heapq.heappop(max_heap)
Or use Python 3.10+ heapify_max():
from heapq import heapify_max, _heappop_max
max_heap = [3, 1, 4, 1, 5]
heapify_max(max_heap)
max_val = _heappop_max(max_heap)
We’ve looked at binary heaps, and some of their operations. The next post is going to be focused on patterns that occur when dealing with binary heap types of problems in interviews.