Heap (Priority Queue)

Always Know What's Next: Heaps & Priority Queues

A Heap is a specialized tree-based data structure that satisfies the heap property. This makes it perfect for implementing a Priority Queue, an abstract data type where each element has a "priority" and the element with the highest priority is always accessed first.

1. Core Concepts

A heap is a complete binary tree, meaning all levels are fully filled except possibly the last, which is filled from left to right. This structure allows it to be efficiently represented by a simple array.

Min-Heap: The value of any node is less than or equal to the values of its children. This means the root is always the smallest element.
Max-Heap: The value of any node is greater than or equal to the values of its children. The root is always the largest element.

Min-Heap vs. Max-Heap

Min-Heap

Root is smallest.

Max-Heap

Root is largest.

2. Heap Operations

The magic of heaps comes from their ability to efficiently maintain the heap property after modifications.

Method	Description	Complexity
push / insert	Adds a new element. This involves placing the element at the end and "bubbling it up" until the heap property is restored.	O(log n)
pop / extract-min/max	Removes and returns the root element. The last element is moved to the root, and then "bubbled down" until the property is restored.	O(log n)
peek / top	Returns the root element without removing it.	O(1)
heapify	Converts an arbitrary array into a heap in-place. A clever bottom-up approach achieves this faster than repeated insertions.	O(n)

3. Classic Problems

Kth Largest Element in an Array

Find the kth largest element. A min-heap of size K is perfect for this. Iterate through the array. For each number, push it to the heap. If the heap's size exceeds K, pop the smallest element. After iterating through all numbers, the root of the min-heap is the Kth largest element.

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]

Find Median from Data Stream

A famous hard design problem. The key is to maintain two heaps: a max-heap to store the smaller half of the numbers and a min-heap to store the larger half. By keeping the heaps balanced (or nearly balanced), the median can always be calculated from the tops of the two heaps in O(1) time.

import heapq

class MedianFinder:
    def __init__(self):
        # Python's heapq is a min-heap.
        # To simulate a max-heap, we store negative numbers.
        self.small_half = []  # max-heap
        self.large_half = []  # min-heap

    def addNum(self, num: int) -> None:
        # Push to max-heap and pop greatest, then push to min-heap
        heapq.heappush(self.small_half, -1 * num)
        
        # Ensure every num in small_half is <= every num in large_half
        if (self.small_half and self.large_half and 
                (-1 * self.small_half[0]) > self.large_half[0]):
            val = -1 * heapq.heappop(self.small_half)
            heapq.heappush(self.large_half, val)

        # Balance the heaps (size of small_half >= size of large_half)
        if len(self.small_half) > len(self.large_half) + 1:
            val = -1 * heapq.heappop(self.small_half)
            heapq.heappush(self.large_half, val)
        if len(self.large_half) > len(self.small_half):
            val = heapq.heappop(self.large_half)
            heapq.heappush(self.small_half, -1 * val)

    def findMedian(self) -> float:
        if len(self.small_half) > len(self.large_half):
            return -1 * self.small_half[0]
        return (-1 * self.small_half[0] + self.large_half[0]) / 2.0

Merge k Sorted Lists

A problem where you merge multiple sorted linked lists into a single sorted list. A min-heap is ideal for this. Insert the head of each of the k lists into the min-heap. Then, repeatedly extract the minimum node from the heap, add it to your result list, and insert the next node from the same list that the extracted node came from.

import heapq

class Solution:
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        min_heap = []
        for i, l in enumerate(lists):
            if l:
                # Add a tie-breaker (the list index i) to handle nodes with the same value
                heapq.heappush(min_heap, (l.val, i, l))
        
        dummy = ListNode()
        tail = dummy
        
        while min_heap:
            val, i, node = heapq.heappop(min_heap)
            tail.next = node
            tail = tail.next
            if node.next:
                heapq.heappush(min_heap, (node.next.val, i, node.next))
                
        return dummy.next

Interactive Min-Heap

Visualize heap operations like insertion (bubble-up) and extraction (bubble-down).

Heap is empty. Insert an element to start.

Click a button to start.