Heaps are special data structures for quickly finding the smallest or largest item in a collection. Like a family tree where parents are always older than their children, the oldest person (most important item) is always at the root. Heaps are binary trees stored as arrays for efficiency, with each array index corresponding to a tree node.

Heaps mainly use two operations: push to add new elements and pop to remove the top one. These keep the heap organized. You can also peek to see the top element without removing it. To create a heap from an unsorted array, we use heapify. Together, these operations maintain the heap’s unique structure and ensure it works efficiently.

The push and pop operations "bubble" elements up or down the heap to maintain their structure and order. This process ensures that after each operation, the element with the highest priority is always at the root of the heap.

Heaps have a unique structure: they’re always complete binary trees. This means all levels of the tree are full, except maybe the last one. If the last level isn’t full, it’s filled from left to right. This structure keeps the tree balanced, ensuring no branch gets too long and the tree’s height stays small.

This allows heaps to be stored efficiently in arrays, without needing extra pointers. This array representation makes finding a node’s relatives simple. 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 property makes heap operations fast and memory-efficient. The structure property ensures that adding or removing elements keeps the heap balanced, which is crucial for maintaining quick access times.

The heap order property is what gives heaps their special ability to quickly find the smallest (or largest) element. In a min heap, each parent node’s value is less than or equal to its children’s values. The opposite is true for a max heap, where parents are greater than or equal to their children.

This property creates a partial ordering of elements. While the heap isn’t actually sorted, it just guarantees that the path from any node to the root is always in order. This means the smallest (in a min heap) or largest (in a max heap) element is always at the root, making it easy to access.

Binary heaps are binary trees with two key features: the structure property, which defines their organization, and the order property, which maintains a sorted order between elements. These properties make binary heaps efficient and easy to use. Heaps, despite being binary trees, are typically built using arrays for memory efficiency and simpler operations.

Binary heaps are typically built using arrays, which makes them easy to work with. We’ll create a BinaryHeap class that stores heap elements in an array. This class will have methods like insert to add new values and find parent or child nodes.

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, allowing us to easily navigate between parent and child nodes using simple math. Starting with index 0 as the root, we can easily find any node’s relatives. For a node at index i, its left child is at 2i + 1, its right child at 2i + 2, and its parent at (i - 1) // 2. This simple math makes operations like inserting new elements or removing the top element efficient.

Heaps come in two fundamental forms: min heaps and max heaps. In a min heap, parent nodes must be smaller than their children, making them perfect for finding the smallest element quickly, like in task scheduling where lower numbers mean higher priority. In a max heap, parent nodes must be larger than their children, making them ideal for applications that need quick access to the largest element, such as maintaining high scores in a game.

The choice between min and max heaps often depends on what you’re tracking. When keeping track of the top k elements , a min heap is actually better for finding the largest elements, while a max heap works better for finding the smallest elements. This is because a min heap can efficiently maintain the k largest values by keeping their smallest value at the root, making it easy to compare with new values. Similarly, a max heap maintains the k smallest values by keeping their largest value readily accessible at the root.

Adding new elements to a heap is like finding someone’s place in a family photo where everyone must stand behind their parents . When we add a new element, we first put it at the end of the heap (bottom-right of the tree) and then let it bubble up to its correct position. This process maintains both the structure and order properties of the heap.

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 ensures that smaller elements (in a min heap) or larger elements (in a max heap) move up towards the root. Each swap brings the element closer to its correct position while maintaining the heap’s properties.

Removing elements from a heap is like moving players in a sports tournament where the best player must always be team captain . When we remove the root element, we replace it with the last element in the heap and let it sink down to maintain proper order. This ensures both the structure and order properties remain 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 ensures that larger elements (in a min heap) or smaller elements (in a max heap) move down away from the root. Each swap moves the element to its proper position while maintaining the heap’s order.

Building a heap from an unsorted array is like organizing a company where every manager must be more qualified than their team members. Instead of adding elements one by one, heapify starts from the bottom of the tree and works upward, ensuring each parent node is in the correct position relative to its children. This process is more efficient than pushing elements individually into the heap.

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 more efficient than building a heap by repeatedly using push because it skips unnecessary comparisons with nodes that will be processed later. By starting from the bottom, we ensure that by the time we process a node, its children are already in their correct positions.

Heaps should be your go-to data structure for keeping track of k smallest (or largest) elements, and supporting operations like finding the minimum or maximum element efficiently. Here are some tips and tricks for using heaps effectively in coding interviews: