11. Heaps and Priority Queues

📋 Jump to Takeaways

A heap answers one question efficiently: what's the smallest (or largest) element right now? Not "find element X" — hash maps do that. Not "give me everything sorted" — sorting does that. Just "give me the extreme value, and let me add/remove elements while maintaining that guarantee." That's O(log n) per operation instead of O(n).

The Structure

A heap is a complete binary tree stored as an array. The heap property: every parent is smaller than (min-heap) or larger than (max-heap) its children.

Min-heap as tree:        As array:
       1                 [1, 3, 2, 7, 4, 5, 6]
      / \
     3   2               Parent of i: (i-1)/2
    / \ / \              Left child:  2*i + 1
   7  4 5  6             Right child: 2*i + 2

No pointers needed. The tree structure is implicit in the array indices. This makes heaps cache-friendly and memory-efficient.

Operations

Push — add to the end, sift up until heap property is restored. O(log n).

Pop — remove the root (min/max), move the last element to root, sift down. O(log n).

Peek — return the root. O(1).

Sift Up and Sift Down

These are the two fundamental heap operations. Everything else is built on them.

// Sift up — after inserting at the end, bubble the element up
func siftUp(heap []int, i int) {
    for i > 0 {
        parent := (i - 1) / 2
        if heap[i] >= heap[parent] {
            break // heap property satisfied
        }
        heap[i], heap[parent] = heap[parent], heap[i]
        i = parent
    }
}

// Sift down — after removing root, bubble the replacement down
func siftDown(heap []int, i, size int) {
    for {
        smallest := i
        left := 2*i + 1
        right := 2*i + 2
        if left < size && heap[left] < heap[smallest] {
            smallest = left
        }
        if right < size && heap[right] < heap[smallest] {
            smallest = right
        }
        if smallest == i {
            break // heap property satisfied
        }
        heap[i], heap[smallest] = heap[smallest], heap[i]
        i = smallest
    }
}

Sift up compares with parent and swaps upward. Sift down compares with both children and swaps with the smaller one. Both are O(log n) because the tree height is log n.

Building a Heap is O(n)

Calling push n times is O(n log n). But building a heap from an existing array is O(n) using sift down from the middle:

func buildHeap(nums []int) {
    n := len(nums)
    // Start from last non-leaf node, sift down each
    for i := n/2 - 1; i >= 0; i-- {
        siftDown(nums, i, n)
    }
}

Why O(n) and not O(n log n)? Most nodes are near the bottom. Leaves (half the nodes) don't sift at all. Nodes one level up sift at most 1 step. Only the root sifts log n steps. The sum converges to O(n).

import "container/heap"

// Go's container/heap interface
type IntHeap []int

func (h IntHeap) Len() int           { return len(h) }
func (h IntHeap) Less(i, j int) bool { return h[i] < h[j] } // min-heap
func (h IntHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }

func (h *IntHeap) Push(x any) { *h = append(*h, x.(int)) }
func (h *IntHeap) Pop() any {
    old := *h
    n := len(old)
    x := old[n-1]
    *h = old[:n-1]
    return x
}

// Usage
h := &IntHeap{5, 3, 8, 1}
heap.Init(h)          // O(n) — heapify
heap.Push(h, 2)       // O(log n)
min := heap.Pop(h)    // O(log n) — returns 1

Go's container/heap is verbose but flexible. You implement the interface, it handles the bubbling.

Priority Queue

A priority queue is the abstract concept — "give me the highest priority item." A heap is the standard implementation. Same thing, different names.

// Task scheduler — process highest priority first
type Task struct {
    Name     string
    Priority int
}

type TaskQueue []Task

func (q TaskQueue) Len() int            { return len(q) }
func (q TaskQueue) Less(i, j int) bool  { return q[i].Priority > q[j].Priority } // max by priority
func (q TaskQueue) Swap(i, j int)       { q[i], q[j] = q[j], q[i] }
func (q *TaskQueue) Push(x any)         { *q = append(*q, x.(Task)) }
func (q *TaskQueue) Pop() any {
    old := *q
    n := len(old)
    x := old[n-1]
    *q = old[:n-1]
    return x
}

Pattern: Top-K Elements

Find the K largest (or smallest) elements from a stream or array. Use a heap of size K.

LeetCode 215 - Kth Largest Element in an Array

import "container/heap"

func findKthLargest(nums []int, k int) int {
    h := &IntHeap{}
    heap.Init(h)
    for _, n := range nums {
        heap.Push(h, n)
        if h.Len() > k {
            heap.Pop(h) // remove smallest, keeping K largest
        }
    }
    return (*h)[0] // smallest of the K largest = Kth largest
}

Maintain a min-heap of size K. After processing all elements, the root is the Kth largest. O(n log k) time, O(k) space.

LeetCode 347 - Top K Frequent Elements

Given an integer array, return the k most frequent elements.

import "container/heap"

type FreqItem struct {
    Val  int
    Freq int
}

type FreqHeap []FreqItem

func (h FreqHeap) Len() int            { return len(h) }
func (h FreqHeap) Less(i, j int) bool  { return h[i].Freq < h[j].Freq } // min by freq
func (h FreqHeap) Swap(i, j int)       { h[i], h[j] = h[j], h[i] }
func (h *FreqHeap) Push(x any)         { *h = append(*h, x.(FreqItem)) }
func (h *FreqHeap) Pop() any {
    old := *h
    n := len(old)
    x := old[n-1]
    *h = old[:n-1]
    return x
}

func topKFrequent(nums []int, k int) []int {
    freq := map[int]int{}
    for _, n := range nums {
        freq[n]++
    }
    h := &FreqHeap{}
    heap.Init(h)
    for val, count := range freq {
        heap.Push(h, FreqItem{val, count})
        if h.Len() > k {
            heap.Pop(h) // evict least frequent
        }
    }
    result := make([]int, h.Len())
    for i := range result {
        result[i] = (*h)[i].Val
    }
    return result
}

Why not sort? Sorting is O(n log n). A heap of size K processes each element in O(log k). When k << n, the heap wins. Also works on streams where you don't have all data upfront.

Pattern: Merge K Sorted Lists

Merge K sorted sequences into one sorted sequence. Push the first element of each list into a min-heap. Pop the smallest, push the next element from that list.

Lists: [1,4,7], [2,5,8], [3,6,9]
Heap:  [1, 2, 3]  → pop 1, push 4
Heap:  [2, 3, 4]  → pop 2, push 5
Heap:  [3, 4, 5]  → pop 3, push 6
...
Result: [1, 2, 3, 4, 5, 6, 7, 8, 9]

O(n log k) where n is total elements and k is number of lists. Without a heap, merging pairs repeatedly is O(n log k) too, but the heap approach is simpler to implement.

LeetCode 23 - Merge K Sorted Lists

import "container/heap"

type ListNode struct {
    Val  int
    Next *ListNode
}

type NodeHeap []*ListNode

func (h NodeHeap) Len() int            { return len(h) }
func (h NodeHeap) Less(i, j int) bool  { return h[i].Val < h[j].Val }
func (h NodeHeap) Swap(i, j int)       { h[i], h[j] = h[j], h[i] }
func (h *NodeHeap) Push(x any)         { *h = append(*h, x.(*ListNode)) }
func (h *NodeHeap) Pop() any {
    old := *h
    n := len(old)
    x := old[n-1]
    *h = old[:n-1]
    return x
}

func mergeKLists(lists []*ListNode) *ListNode {
    h := &NodeHeap{}
    heap.Init(h)
    for _, l := range lists {
        if l != nil {
            heap.Push(h, l)
        }
    }
    dummy := &ListNode{}
    curr := dummy
    for h.Len() > 0 {
        node := heap.Pop(h).(*ListNode)
        curr.Next = node
        curr = curr.Next
        if node.Next != nil {
            heap.Push(h, node.Next)
        }
    }
    return dummy.Next
}

The heap always contains at most K nodes (one per list). Each pop and push is O(log k), and we process all n nodes, giving O(n log k) total.

Pattern: Running Median (Two Heaps)

Maintain a max-heap for the lower half and a min-heap for the upper half. The median is always at the top of one or both heaps.

Stream: 5, 2, 8, 1, 9

After 5:  maxHeap=[5]      minHeap=[]       median=5
After 2:  maxHeap=[2]      minHeap=[5]      median=3.5
After 8:  maxHeap=[2]      minHeap=[5,8]    median=5
After 1:  maxHeap=[1,2]    minHeap=[5,8]    median=3.5
After 9:  maxHeap=[1,2]    minHeap=[5,8,9]  median=5

Each insertion is O(log n). Getting the median is O(1). Without heaps, you'd need to sort after every insertion — O(n log n) per element.

LeetCode 295 - Find Median from Data Stream

import "container/heap"

type MaxHeap []int // lower half

func (h MaxHeap) Len() int            { return len(h) }
func (h MaxHeap) Less(i, j int) bool  { return h[i] > h[j] } // max-heap
func (h MaxHeap) Swap(i, j int)       { h[i], h[j] = h[j], h[i] }
func (h *MaxHeap) Push(x any)         { *h = append(*h, x.(int)) }
func (h *MaxHeap) Pop() any {
    old := *h
    n := len(old)
    x := old[n-1]
    *h = old[:n-1]
    return x
}

type MinHeap []int // upper half

func (h MinHeap) Len() int            { return len(h) }
func (h MinHeap) Less(i, j int) bool  { return h[i] < h[j] }
func (h MinHeap) Swap(i, j int)       { h[i], h[j] = h[j], h[i] }
func (h *MinHeap) Push(x any)         { *h = append(*h, x.(int)) }
func (h *MinHeap) Pop() any {
    old := *h
    n := len(old)
    x := old[n-1]
    *h = old[:n-1]
    return x
}

type MedianFinder struct {
    lo MaxHeap // max-heap — lower half
    hi MinHeap // min-heap — upper half
}

func Constructor() MedianFinder {
    return MedianFinder{}
}

func (mf *MedianFinder) AddNum(num int) {
    heap.Push(&mf.lo, num)
    // ensure max of lo <= min of hi
    heap.Push(&mf.hi, heap.Pop(&mf.lo))
    // balance: lo can have at most 1 more than hi
    if mf.hi.Len() > mf.lo.Len() {
        heap.Push(&mf.lo, heap.Pop(&mf.hi))
    }
}

func (mf *MedianFinder) FindMedian() float64 {
    if mf.lo.Len() > mf.hi.Len() {
        return float64(mf.lo[0])
    }
    return float64(mf.lo[0]+mf.hi[0]) / 2.0
}

Every AddNum does at most 3 heap operations — O(log n). FindMedian peeks at roots — O(1).

Operation Costs

Operation Heap Sorted Array Unsorted Array
Find min/max O(1) O(1) O(n)
Insert O(log n) O(n) O(1)
Extract min/max O(log n) O(1)* O(n)
Build from array O(n) O(n log n) O(1)

*O(1) if removing from the end of a sorted array.

The heap is the sweet spot: fast extraction AND fast insertion.

When to Use Heaps

  • "Give me the K largest/smallest" → min/max heap of size K
  • Scheduling by priority → priority queue
  • Merging sorted streams → min-heap
  • Running statistics (median, percentiles) → two heaps
  • Dijkstra's shortest path → min-heap of distances
  • Huffman coding → min-heap of frequencies

When NOT to Use Heaps

  • You need to search for arbitrary elements → hash map
  • You need all elements sorted → just sort the array
  • You only need min OR max once → linear scan is O(n) and simpler
  • You need the kth element once from static data → quickselect is O(n) average

Practice Problems

Problem Difficulty Link
Kth Largest Element in an Array Medium LeetCode 215
Top K Frequent Elements Medium LeetCode 347
Merge K Sorted Lists Hard LeetCode 23
Find Median from Data Stream Hard LeetCode 295
Task Scheduler Medium LeetCode 621
Last Stone Weight Easy LeetCode 1046

Key Takeaways

  • A heap is a complete binary tree stored as an array — parent at (i-1)/2, children at 2i+1 and 2i+2
  • Min-heap gives O(1) access to the minimum, O(log n) insert and extract
  • Go's container/heap requires implementing a 5-method interface
  • Top-K, merge K sorted, and running median are the three core heap patterns
  • Heaps are the standard implementation of priority queues
  • Use heaps when you need repeated access to the extreme value with dynamic insertions

📝 Ready to test your knowledge?

Answer the quiz below to mark this lesson complete.

Spot something off? Report an issue

© 2026 ByteLearn.dev. Free courses for developers. · Privacy
☕