Module 6.3 ⏱ 45 min read ⚡ Heaps & Priority Queues

Heaps & Priority Queues

Master complete binary tree properties, min-heap/max-heap heapify operations, and priority queue applications like Kth largest elements and merging sorted lists.

1. Complete Binary Tree Properties & Heap Invariants

A heap is a specialized tree-based data structure that satisfies the heap property: in a min-heap, for any given node $i$, the key is less than or equal to its children, meaning the smallest element is always at the root. Conversely, a max-heap maintains keys greater than or equal to its children, keeping the largest element at the root.

Array Storage: Heaps are almost exclusively implemented using contiguous arrays without pointer overhead. For any element at index $i$:

Left child index: $2i + 1$
Right child index: $2i + 2$
Parent index: $\lfloor (i - 1) / 2 \rfloor$

2. Heapify Operations & Priority Queues

Dynamic modifications rely on two core maintenance routines:

Sift-Up (Bubble-Up): When a new element is inserted at the end of the array, it bubbles up by comparing against its parent and swapping if the heap property is violated, taking $O(\log n)$ time.

Sift-Down (Bubble-Down): When the root element is popped and replaced by the last element, it sinks down by swapping with its smaller (min-heap) or larger (max-heap) child, running in $O(\log n)$ time. Building a heap from an arbitrary array via bottom-up heapify runs in linear $O(n)$ time.

// C++ Solution: Kth Largest Element in an Array (Min-Heap Approach)
#include <vector>
#include <queue>

class Solution {
public:
    int findKthLargest(std::vector<int>& nums, int k) {
        std::priority_queue<int, std::vector<int>, std::greater<int>> minHeap;
        for (int num : nums) {
            minHeap.push(num);
            if (minHeap.size() > k) {
                minHeap.pop();
            }
        }
        return minHeap.top();
    }
};
            

# Python Solution: Kth Largest Element in an Array (Min-Heap Approach)
import heapq

class Solution:
    def findKthLargest(self, nums: list[int], k: int) -> int:
        min_heap = []
        for num in nums:
            heapq.heappush(min_heap, num)
            if len(min_heap) > k:
                heapq.heappop(min_heap)
        return min_heap[0]
            

// Java Solution: Kth Largest Element in an Array (Min-Heap Approach)
import java.util.PriorityQueue;

class Solution {
    public int findKthLargest(int[] nums, int k) {
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        for (int num : nums) {
            minHeap.offer(num);
            if (minHeap.size() > k) {
                minHeap.poll();
            }
        }
        return minHeap.peek();
    }
}
            

3. Homework & Quiz Overview

To lock in your mastery, complete the implementation exercises for finding the Kth largest element in an array and Merging $k$ sorted lists.

Quick Check: Test Your Intuition

What is the time complexity of building a heap from an unsorted array of size $n$ using the bottom-up `heapify` algorithm?