A heap is 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. 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. These operations are how the heap keeps its structure and order properties intact.

The push and popoperations "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 arrayswithout 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. As elements get added or removed, the structure property keeps the tree balanced, so access times stay short.

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.

This property creates a partial ordering of elements. The heap isn't actually sorted. It just guarantees that the path from any node to the root is always in order. So the smallest element (in a min heap) or largest element (in a max heap) is always at the root, ready to grab.

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 insertnew 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 0as 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. That keeps both the structure and order properties intact.

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 pushes the element closer to its correct spot while keeping the heap valid.

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 a lot more efficient than calling push repeatedly.

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.

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:

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: