Heap

Problem¶

• Define heaps.
• Why we need heaps in practice?
• When is it the right data structure?
• Provide a simple Python implementation.

Definition¶

A heap is a tree-like data structure usually stored in an array, with one key rule:

• Min-heap:
  • Every parent is <= its children.
  • So the smallest value is always at the root.
• Max-heap:
  • Every parent is >= its children.
  • So the largest value is always at the root.

Important:

• A heap is not sorted.
• It only guarantees that the top element is easy to access.
• That is why it is great when you repeatedly need:
  • the smallest element
  • the largest element
  • the top k elements

Intuition¶

A sorted array gives you everything in order, but keeping it sorted is expensive.

A heap gives you only what you need most:

• "What is the smallest right now?"
• "What is the largest right now?"

and lets you update that efficiently.

Why heaps are useful in practice¶

Heaps are useful when the problem is about a changing "best" element.

Typical uses:

• Priority queues
  • "Always process the most urgent task next"
• Top k problems
  • k largest
  • k smallest
• Scheduling
  • next job to run
  • earliest finishing event
• Graph algorithms
  • Dijkstra
  • Prim
• Streaming data
  • numbers arrive one by one, but you still want current top k

When a heap is the right data structure¶

Use a heap when:

• You need repeated access to min or max.
• Data changes over time.
• You do not need the whole collection sorted.
• You want better than:
  • repeatedly scanning for min/max, which is \(O(n)\) each time
  • re-sorting after every insertion

A heap is often the right choice when the sentence sounds like:

• "keep track of the largest/smallest as we go"
• "repeatedly remove the next best item"
• "maintain top k"

Time idea¶

If you sort everything:

• \(O(n \log n)\)

If you keep a heap of size k:

• each update costs about \(O(\log k)\)
• total is \(O(n \log k)\)

This is much better when k is small compared to n.

How a heap is stored¶

Usually in an array.

Example heap array:

[2, 5, 3, 8, 7, 6]

This means:

        2
      /   \
     5     3
    / \   /
   8   7 6

Index relationships:

• left child of i is 2*i + 1
• right child of i is 2*i + 2
• parent of i is (i - 1) // 2

That is why heaps are simple and efficient in arrays.

The two core operations¶

1. Push¶

Add a new value:

• put it at the end
• "bubble up" while heap rule is broken

2. Pop min¶

Remove smallest value from a min-heap:

• remove root
• move last value to root
• "bubble down" while heap rule is broken

Simplest heap implementation in Python¶

Below is a tiny min-heap implementation from scratch.

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

    def peek(self):
        return self.data[0]

    def push(self, x):
        self.data.append(x)
        self._sift_up(len(self.data) - 1)

    def pop(self):
        if not self.data:
            raise IndexError("pop from empty heap")

        smallest = self.data[0]
        last = self.data.pop()

        if self.data:
            self.data[0] = last
            self._sift_down(0)

        return smallest

    def _sift_up(self, i):
        while i > 0:
            parent = (i - 1) // 2
            if self.data[i] < self.data[parent]:
                self.data[i], self.data[parent] = self.data[parent], self.data[i]
                i = parent
            else:
                break

    def _sift_down(self, i):
        n = len(self.data)

        while True:
            left = 2 * i + 1
            right = 2 * i + 2
            smallest = i

            if left < n and self.data[left] < self.data[smallest]:
                smallest = left

            if right < n and self.data[right] < self.data[smallest]:
                smallest = right

            if smallest == i:
                break

            self.data[i], self.data[smallest] = self.data[smallest], self.data[i]
            i = smallest

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

The key idea in one sentence¶

A min-heap of size k lets you keep exactly the k largest values seen so far, and the smallest among them is the answer.

In real Python interviews¶

You almost always use heapq, not a hand-written heap.

Example 215. Kth Largest Element in an Array:

import heapq

class Solution:
    def findKthLargest(self, nums: list[int], k: int) -> int:
        heap = []

        for x in nums:
            if len(heap) < k:
                heapq.heappush(heap, x)
            elif x > heap[0]:
                heapq.heapreplace(heap, x)

        return heap[0]

Follow this mental model:

• sorting = "I need all order information"
• heap = "I only need the current best element, and I need to update it often"