Binary Heaps and Priority Queues

Concept 1: The Anatomy of a Binary Heap

While a binary heap is a tree, it follows a completely different set of rules than a Binary Search Tree. Its power comes from a unique combination of structural and ordering properties.

Technical Explanation

A binary heap is a complete binary tree that satisfies the heap property.

1. Shape Property (Complete Binary Tree): This means the tree is fully filled on all levels, except possibly the last level, where nodes are filled from left to right. This structural rigidity is key because it allows us to represent the tree efficiently in a simple array, without needing explicit node objects with left and right pointers.

2. Heap Property (Parent-Child Ordering):

   • In a Min-Heap, the value of each node is less than or equal to the value of its children. This guarantees the smallest element is always at the root.
   • In a Max-Heap, the value of each node is greater than or equal to the value of its children. This guarantees the largest element is always at the root.

Because of the complete tree structure, we can map any node to an array index and navigate between parent and children using simple arithmetic:
For a node at index i:

• Parent: (i - 1) // 2
• Left Child: 2 * i + 1
• Right Child: 2 * i + 2

To see these concepts explained visually, the following video provides a concise overview.

Metaphor: The Corporate Hierarchy

Think of a heap as a perfectly structured corporate org chart.

• Shape Property (Complete Tree): The company fills every position on a management level before starting the next level down. There are no empty desks in the middle of a row.
• Heap Property (Ordering): In a "min-heap" company, seniority is based on employee ID number; every manager has a lower ID than their direct reports. The CEO has employee ID #1. In a "max-heap" company, it's based on salary; every manager earns more than their reports, and the CEO is the highest-paid person.

This structure means you can find the person with the "highest priority" (lowest ID or highest salary) in $O(1)$ time—they're always at the top.

Python Code Snippet: Helper Methods

When implementing a heap class, we start with these essential helper methods for navigation.

class MinHeap:
    def __init__(self):
        # Initialize an empty list to store heap elements.
        self.heap = []

    def _get_parent_index(self, i):
        return (i - 1) // 2

    def _get_left_child_index(self, i):
        return 2 * i + 1

    def _get_right_child_index(self, i):
        return 2 * i + 2

    def _has_parent(self, i):
        return self._get_parent_index(i) >= 0

    def _has_left_child(self, i):
        return self._get_left_child_index(i) < len(self.heap)

    def _has_right_child(self, i):
        return self._get_right_child_index(i) < len(self.heap)

    def _swap(self, i, j):
        self.heap[i], self.heap[j] = self.heap[j], self.heap[i]

Concept 2: Core Heap Mechanics: Sift-Up and Sift-Down

A heap's state is dynamic. When you add or remove elements, you might temporarily violate the heap property. Two fundamental operations, sift-up and sift-down, are used to restore order.

Technical Explanation

1. Sift-Up (or Bubble-Up, Heapify-Up): Used after inserting a new element. A new element is added to the end of the array (the first available spot on the last level). It might be smaller than its parent (in a min-heap), violating the heap property. Sift-up repeatedly compares the element with its parent and swaps them if they are in the wrong order, moving the element up the tree until it reaches its correct position or becomes the new root.

2. Sift-Down (or Bubble-Down, Heapify-Down): Used after removing the root element. To remove the root, we can't just leave a hole. We move the last element in the array into the root's position. This new root is likely out of place. Sift-down compares the new root with its children and swaps it with the smaller child (in a min-heap), moving it down the tree until it's smaller than both its children or becomes a leaf.

Both operations traverse a path from the root to a leaf (or vice-versa), so their time complexity is proportional to the height of the tree. Since a complete binary tree is always balanced, its height is ${\log }_{2}N$. Therefore, both sift-up and sift-down have a time complexity of $O(\log N)$.

Metaphor: Performance Reviews in the Hierarchy

• Sift-Up (Promotion): A new hire joins at the bottom of the org chart. They are a star performer, outshining their manager. The company "sifts them up" by promoting them, swapping their position with their manager. This continues until their manager is finally more senior/higher-paid (the heap property is restored).
• Sift-Down (Re-organization): The CEO leaves. To fill the spot quickly, the newest hire is temporarily placed in the CEO's office. This new "CEO" is clearly not qualified. The board "sifts them down" by swapping them with their most qualified direct report. This process repeats, moving the unqualified person down the hierarchy until they land in a role where they are more senior/higher-paid than their reports (or have no reports).

Python Code Snippet: sift_up and sift_down

Let's add these methods to our MinHeap class.

class MinHeap:
    # ... (previous helper methods) ...

    def _sift_up(self):
        # Start with the last element
        index = len(self.heap) - 1
        # While it has a parent and is smaller than its parent, swap up
        while self._has_parent(index) and self.heap[index] < self.heap[self._get_parent_index(index)]:
            parent_index = self._get_parent_index(index)
            self._swap(index, parent_index)
            index = parent_index # Move up to the parent's index

    def _sift_down(self):
        # Start with the root
        index = 0
        # Loop as long as there is at least a left child to compare with
        while self._has_left_child(index):
            smaller_child_index = self._get_left_child_index(index)
            # If a right child exists and is smaller than the left, it's our target
            if self._has_right_child(index) and self.heap[self._get_right_child_index(index)] < self.heap[smaller_child_index]:
                smaller_child_index = self._get_right_child_index(index)
            
            # If the current node is smaller than its smallest child, we're done
            if self.heap[index] < self.heap[smaller_child_index]:
                break
            else:
                self._swap(index, smaller_child_index)
            
            index = smaller_child_index # Move down to the smaller child's index

Concept 3: Public Methods: insert, peek, and poll

With the core mechanics in place, building the public API for our heap (which acts as a priority queue) is straightforward.

Technical Explanation

• peek(): Returns the highest-priority element. In a min-heap, this is the minimum value. Since it's always at the root (index 0), this is an $O(1)$ operation.
• insert(item): Adds a new item. This involves two steps:
  1. Append the item to the end of the array. ($O(1)$ amortized)
  2. Call _sift_up() to restore the heap property. ($O(\log N)$)
     The total complexity is dominated by sift-up: $O(\log N)$.
• poll() (or extract_min): Removes and returns the highest-priority element. This is the most complex operation:
  1. Save the root element to be returned later. ($O(1)$)
  2. Move the last element of the array to the root position (index 0). ($O(1)$)
  3. Remove the last element from the array. ($O(1)$)
  4. Call _sift_down() on the new root to restore the heap property. ($O(\log N)$)
     The total complexity is dominated by sift-down: $O(\log N)$.

This article provides the full implementation details for these methods.

Python Code Snippet: Completing the MinHeap Class

import sys

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

    # ... (all _helper and _sift methods from before) ...

    def peek(self):
        """Returns the smallest item without removing it."""
        if not self.heap:
            raise IndexError("peek from an empty heap")
        return self.heap[0]

    def poll(self):
        """Removes and returns the smallest item from the heap."""
        if not self.heap:
            raise IndexError("poll from an empty heap")
        
        item = self.heap[0]
        # Move the last element to the root
        self.heap[0] = self.heap[-1]
        self.heap.pop()
        # Restore heap property
        self._sift_down()
        return item

    def add(self, item):
        """Adds a new item to the heap."""
        self.heap.append(item)
        # Restore heap property
        self._sift_up()

    def __len__(self):
        return len(self.heap)

Concept 4: Building a Heap in Linear Time (Heapify)

What if you're given an existing array of numbers and need to turn it into a heap? You could insert each element one by one, but there's a much faster way.

Technical Explanation

1. Naive Approach: Create an empty heap and call insert() for each of the $N$ elements in the input array. Since each insertion is $O(\log N)$, the total time complexity is $O(N\log N)$.

2. Optimized Approach (Floyd's Algorithm): A more clever, bottom-up approach achieves a surprising $O(N)$ linear time complexity.

   • Treat the input array as a complete-but-unordered binary tree.
   • The leaf nodes (the entire second half of the array) already satisfy the heap property by themselves.
   • Start from the last non-leaf node and iterate backwards to the root.
   • At each node, perform a sift-down operation.

The reason this is $O(N)$ is counter-intuitive. While a single sift-down can be $O(\log N)$, most of the elements are near the bottom of the tree. The vast majority of nodes will only sift down a few levels, or not at all. A formal proof shows that the sum of the work done at each level converges to a value proportional to $N$.

This is a critical "under the hood" optimization that interviewers at top companies love to probe.

Python Code Snippet: The _heapify method

Let's modify our MinHeap to support initialization from a list in $O(N)$ time.

class MinHeap:
    def __init__(self, iterable=None):
        if iterable:
            self.heap = list(iterable)
            self._heapify()
        else:
            self.heap = []
    
    def _heapify(self):
        # Start from the last non-leaf node and sift down.
        last_non_leaf_index = (len(self.heap) - 2) // 2
        for i in range(last_non_leaf_index, -1, -1):
            # We need to modify _sift_down to take an index.
            self._sift_down_from(i)

    def _sift_down_from(self, index):
        # This is a modified sift_down that starts from a given index
        while self._has_left_child(index):
            smaller_child_index = self._get_left_child_index(index)
            if self._has_right_child(index) and self.heap[self._get_right_child_index(index)] < self.heap[smaller_child_index]:
                smaller_child_index = self._get_right_child_index(index)
            
            if self.heap[index] < self.heap[smaller_child_index]:
                break
            else:
                self._swap(index, smaller_child_index)
            
            index = smaller_child_index
    
    # ... other methods ...

Concept 5: Application - Finding the Kth Largest Element

This is a classic interview problem that perfectly showcases the power of heaps.

Technical Explanation

The problem is: "Given an unsorted array nums and an integer k, find the kth largest element."

A naive approach would be to sort the array in descending order ($O(N\log N)$) and pick the element at index k-1. We can do better.

The optimal solution uses a min-heap of size K.

• Iterate through the input array nums.
• For each number, push it onto the min-heap.
• If the heap's size grows larger than k, poll() the smallest element.
• After iterating through all numbers, the heap contains the k largest elements from the array.
• The root of the min-heap is the smallest of these k elements, which is precisely the kth largest element overall.

The time complexity is $O(N\log K)$ because we perform $N$ operations, and each heap operation (add/poll) takes $O(\log K)$ time on a heap of size K. The space complexity is $O(K)$ to store the heap. This is significantly better than $O(N\log N)$ if K is much smaller than N.

Metaphor: The VIP Lounge Bouncer

Imagine you're a bouncer for a VIP lounge with a strict capacity of K people. Your goal is to always have the K "most important" (largest value) guests inside.

1. Guests arrive one by one. You let each one into the lounge.
2. Each time a new guest enters, you check the capacity. If there are now K+1 guests, you must ask one to leave.
3. To maintain the most exclusive group, you find the "least important" guest currently in the lounge (the minimum value among the top K) and ask them to leave.
4. After you've processed every guest at the door, the "least important" person remaining in the lounge is, by definition, the Kth most important person overall.

The min-heap is your perfect tool for instantly identifying that "least important guest in the lounge."

Python Code Snippet: Using heapq

In an interview, you'll almost always use the built-in library for heaps, heapq, which implements a min-heap.

import heapq

def find_kth_largest(nums: list[int], k: int) -> int:
    # Python's heapq is a min-heap. We'll use it to keep track of the
    # k largest elements seen so far.
    min_heap = []
    
    for num in nums:
        # Push the current element onto the heap
        heapq.heappush(min_heap, num)
        
        # If the heap now has more than k elements, remove the smallest one
        if len(min_heap) > k:
            heapq.heappop(min_heap)
            
    # The root of the heap is the smallest of the k largest elements,
    # which is the kth largest element overall.
    return min_heap[0]

# Example from the problem description
nums = [3, 2, 1, 5, 6, 4]
k = 2
print(f"The {k}th largest element is: {find_kth_largest(nums, k)}") # Output: 5

nums = [3, 2, 3, 1, 2, 4, 5, 5, 6]
k = 4
print(f"The {k}th largest element is: {find_kth_largest(nums, k)}") # Output: 4

Conclusion

You have now mastered the binary heap, a fundamental data structure. You've gone "under the hood" to implement it from scratch, understanding the critical sift-up and sift-down operations, and analyzed the linear-time heapify algorithm. Most importantly, you've applied this knowledge to solve a classic interview problem.

Key Takeaways:

• Heap = Complete Tree + Heap Property: This combination allows for efficient array-based implementation.
• Priority Queues: Heaps are the default implementation for priority queues, providing $O(\log N)$ insertions and deletions and $O(1)$ peeks.
• Sifting is Key: sift-up (for insertion) and sift-down (for deletion) are the $O(\log N)$ workhorses that maintain the heap property.
• O(N) Heapify: Building a heap from an array is a linear-time operation, a crucial optimization to remember.
• Kth Element Pattern: Use a heap of size K to solve "Kth largest/smallest" problems in $O(N\log K)$ time. Use a min-heap for Kth largest, and a max-heap for Kth smallest.

Preview of the Next Lesson

Having explored various tree structures, we'll now focus on a problem that requires navigating the relationships between nodes: finding the Lowest Common Ancestor (LCA) of two nodes in both a binary tree and a BST. This is another interview favorite that tests your ability to reason about paths and ancestry in a tree.