A BST keeps everything ordered, and you pay for that order on every insert. But a lot of problems only ever ask one question: what's the smallest (or largest) item right now? A task scheduler grabs the most urgent job. A shortest-path algorithm grabs the closest unvisited node. Maintaining a fully sorted collection just to read the front of it is paying for far more than you use.

A heap is the cheaper deal: a data structure for quickly finding the smallest or largest item in a collection. Think of a family tree where parents are always older than their children. The oldest person (the highest-priority item) sits at the root. Notice what the rule doesn't say: it never compares siblings to each other. That looseness is the whole trick, and we'll come back to it. Heaps are binary trees stored as arrays for efficiency, with each array index lining up with a tree node.

Heaps mainly use two operations: push to add a new element and pop to remove the top one. There's also peek, which looks at the top element without removing it, and heapify, which turns an unsorted array into a heap. Before the table, get a feel for the costs. In a million-element heap, peek is a single array read, because the answer always sits at index 0. And since a complete tree with a million nodes is only about 20 levels deep, a push or pop touches at most 20 nodes on its way up or down:

The push and pop operations "bubble" elements up or down the heap to maintain their structure and order. After every operation, the highest-priority element ends up at the root of the heap.

Heaps are always complete binary trees. That means every level of the tree is full except possibly the last one. If the last level isn't full, it's filled from left to right. This keeps the tree balanced, so no branch gets too long and the height stays small.

Because heaps are complete binary trees, we can store them efficiently in arrays without needing extra pointers. The array representation also makes finding a node's relatives easy. For a node at index i:

• Its left child is at index 2i + 1
• Its right child is at index 2i + 2
• Its parent is at index (i - 1) // 2

This is why heap operations stay fast and memory-efficient. Elements can come and go, but the completeness rule never lets any branch straggle, so the work per operation stays small.

The heap order property is what lets heaps find the smallest (or largest) element so quickly. In a min heap, each parent node's value is less than or equal to its children's values. A max heap is the opposite: parents are greater than or equal to their children.

You might assume a structure this good at finding the minimum must be sorted. It isn't. The heap isn't actually sorted: the rule binds parents to children and says nothing about siblings, so it only guarantees that the path from any node up to the root is in order. Test yourself: in a min heap, where can the second-smallest element live? It has to be one of the root's two children, since the root is the only value smaller than it. But the third-smallest could sit on either side of the tree, two levels down. The smallest element (in a min heap) or largest (in a max heap) is always at the root, ready to grab, and that's the only promise a heap makes.

A binary heap is a binary tree governed by two rules: the structure property, which defines how the tree is laid out, and the order property, which keeps elements partially sorted. Even though they're binary trees, binary heaps are usually implemented as arrays. Arrays use less memory than node-based trees and make the math for navigating between parent and child nodes a lot simpler.

We'll build a BinaryHeap class backed by an array, with methods to insert new values and to find each node's parent and children.

class BinaryHeap:
    def __init__(self):
        # Initialize an empty list for the heap
        self.heap = []

    def insert(self, value: int) -> None:
        # Add the new value to the end of the array
        self.heap.append(value)

    def get_left_child(self, index: int) -> Optional[int]:
        # Calculate the index of the left child
        left_index = 2 * index + 1
        # Check if the left child is within the array
        if left_index < len(self.heap):
            return self.heap[left_index]
        return None

    def get_right_child(self, index: int) -> Optional[int]:
        # Calculate the index of the right child
        right_index = 2 * index + 2
        # Check if the right child is within the array
        if right_index < len(self.heap):
            return self.heap[right_index]
        return None

    def get_parent(self, index: int) -> Optional[int]:
        if index > 0:
            # Calculate the index of the parent node
            parent_index = (index - 1) // 2
            return self.heap[parent_index]
        return None

Each array index corresponds to a position in the tree. Starting with index 0 as the root, you can find any node's relatives with simple math: a node at index i has its left child at 2i + 1, its right child at 2i + 2, and its parent at (i - 1) // 2. That math is what makes operations like insert and pop fast.

Heaps come in two flavors: min heaps and max heaps. In a min heap, parents must be smaller than their children, so the smallest element sits at the root. This is handy for task scheduling, where lower numbers mean higher priority. In a max heap, parents must be larger than their children, so the largest element is the one you can grab quickly. Think tracking high scores in a game.

The choice between min and max heaps depends on what you're tracking, and one part of this trips a lot of people up. When you want the top k largest elements, a min heap is actually better. When you want the top k smallest elements, a max heap is better. The reason: a min heap holds the k largest values by keeping their smallest at the root, so any new value can be compared against that root in O(1) time. Likewise, a max heap holds the k smallest values by keeping their largest at the root, ready to evict.

Adding an element to a heap is like finding your place in a family photo where everyone has to stand behind their parents. We first put the new element at the end of the heap (the bottom-right of the tree) and then let it bubble up to its correct spot. This keeps both the structure and order properties intact.

class MinHeap:
    def __init__(self):
        self.heap = []
    
    def heappush(self, value: int) -> None:
        # Step 1: Add new value to the end of the heap
        self.heap.append(value)
        
        # Get the index of the newly added value
        index = len(self.heap) - 1
        
        # Step 2: "Bubble up" until heap property is restored
        while index > 0:
            # Calculate the parent using formula: (i - 1) // 2
            parent = (index - 1) // 2
            
            # Stop if heap property is satisfied
            if self.heap[parent] <= self.heap[index]:
                break
                
            # Swap with parent if parent is larger (min heap property)
            self.heap[index], self.heap[parent] = self.heap[parent], self.heap[index]
            
            # Move up to parent's position
            index = parent

This "bubble-up" process moves smaller elements (in a min heap) or larger elements (in a max heap) toward the root. Each swap brings the new element one step closer to its correct spot while keeping the heap valid.

Removing an element from a heap is like a sports tournament where the best player always has to be team captain. To remove the root, we replace it with the last element in the heap and let that element sink down to its correct spot. Taking the last element keeps the tree complete, and the sink-down repairs the order.

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

    def heappop(self) -> int:
        # Step 1: Handle empty heap case
        if not self.heap:
            return -1
        
        # Step 2: Store the minimum value to return later
        min_value = self.heap[0]
        
        # Step 3: Move the last element to the root
        last_value = self.heap.pop()
        
        # If heap is not empty after pop, restore heap property
        if self.heap:
            self.heap[0] = last_value
            index = 0
            heap_size = len(self.heap)
            
            # Step 4: "Sink down" until heap property is restored
            while True:
                # Calculate indices of left and right children
                left_child = 2 * index + 1
                right_child = 2 * index + 2
                smallest = index
                
                # Find the smallest value among parent and children
                if left_child < heap_size and self.heap[left_child] < self.heap[smallest]:
                    smallest = left_child
                if right_child < heap_size and self.heap[right_child] < self.heap[smallest]:
                    smallest = right_child
                    
                # If current node is already the smallest, stop
                if smallest == index:
                    break
                    
                # Swap with smallest child
                self.heap[index], self.heap[smallest] = self.heap[smallest], self.heap[index]
                
                # Move down to the smallest child's position
                index = smallest
        
        return min_value

This "sink-down" process moves larger elements (in a min heap) or smaller elements (in a max heap) down away from the root. Each swap drops it one level, and it settles the moment neither child outranks it.

Building a heap from an unsorted array is like organizing a company where every manager has to be more qualified than their team. Instead of adding elements one by one, heapify starts from the bottom of the tree and works upward, fixing each parent's position relative to its children as it goes. It's an entire log factor cheaper than calling push over and over.

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

    def heapify(self, value: int) -> None:
        # Step 1: Add the new value to the end of the heap
        self.heap.append(value)
        
        # Step 2: Get the index of the newly added element
        index = len(self.heap) - 1
        
        # Step 3: "Bubble up" until heap property is restored
        while index > 0:
            # Calculate parent index
            parent_index = (index - 1) // 2
            
            # If parent is smaller than current, heap property is satisfied
            if self.heap[parent_index] <= self.heap[index]:
                break
                
            # Swap with parent if parent is larger
            self.heap[index], self.heap[parent_index] = self.heap[parent_index], self.heap[index]
            
            # Move up to parent's position
            index = parent_index

This "heapify" process is faster than building a heap with repeated calls to push because it skips unnecessary comparisons with nodes that will be processed later. By starting at the bottom, we know that by the time we process any node, its children are already in their correct spots. Half of all nodes are leaves that never move at all, which is how heapify lands at O(n) while building the same heap with n pushes would cost O(n log n).

Heaps are the right tool whenever you need to track the k smallest (or largest) elements, or to quickly grab the minimum or maximum from a collection. Here are a few tips for using them well in coding interviews:

First, two checks from this page: why is peek O(1) but pop O(log n)? And for the top k largest elements, why do you reach for a min heap? If both come back quickly, you're ready. Heaps shine when you only need the minimum or maximum, not full sorting. Once you spot the "top K" or "running min/max" pattern, these problems become satisfying to solve. Work through them to internalize when a heap turns an O(n log n) sort into an O(n log k) scan: