DSA Interview Prep · Lesson

Heapify, Push, and Pop from Scratch

Implement heapify-up for push and heapify-down for pop, then build a heap from an unsorted array in O(n) using Floyd's algorithm.

Building a MinHeap Class

Implementing a heap from scratch demonstrates mastery of the underlying mechanics and is occasionally asked in senior interviews. A MinHeap class wraps an array and exposes push, pop, peek, and size operations. Internally it maintains the heap property by calling sift-up after push and sift-down after pop. Understanding this implementation makes Python's heapq module completely transparent.

class MinHeap:
    def __init__(self):
        self._data = []

    def push(self, val):
        self._data.append(val)
        self._sift_up(len(self._data) - 1)

    def pop(self):
        if len(self._data) == 1:
            return self._data.pop()
        min_val = self._data[0]
        self._data[0] = self._data.pop()  # move last to root
        self._sift_down(0)
        return min_val

    def peek(self):
        return self._data[0] if self._data else None

    def size(self):
        return len(self._data)

    def _parent(self, i): return (i - 1) // 2
    def _left(self, i):   return 2 * i + 1
    def _right(self, i):  return 2 * i + 2

print('MinHeap class skeleton defined')

Implementing Sift-Up

Sift-up compares a node with its parent and swaps upward as long as the heap property (parent <= child for min-heap) is violated. The key is that the newly inserted element is at the end and bubbles up to its correct position. The while loop runs at most floor(log n) times — the height of the tree. Assign i = parent at each step to continue moving up.

class MinHeap:
    def __init__(self):
        self._data = []

    def _parent(self, i): return (i - 1) // 2
    def _left(self, i):   return 2 * i + 1
    def _right(self, i):  return 2 * i + 2

    def _sift_up(self, i):
        while i > 0:
            p = self._parent(i)
            if self._data[p] > self._data[i]:  # parent > child: swap
                self._data[p], self._data[i] = self._data[i], self._data[p]
                i = p
            else:
                break  # heap property satisfied

    def push(self, val):
        self._data.append(val)
        self._sift_up(len(self._data) - 1)

h = MinHeap()
for v in [5, 3, 8, 1, 4]:
    h.push(v)
print(h._data)  # valid min-heap

All lessons in this course

← Back to DSA Interview Prep