Kth Smallest Element Using Min Heap in DSA Go

Mental Model

We use a min heap to always get the smallest number quickly. By removing the smallest number k times, the last one removed is the kth smallest.

Analogy: Imagine a pile of numbered cards. You keep picking the smallest card from the pile one by one. The card you pick on the kth turn is the kth smallest.

Min Heap Array: [2, 3, 5, 7, 8]
Heap structure:
      2
     / \
    3   5
   / \
  7   8

Dry Run Walkthrough

Input: array: [7, 10, 4, 3, 20, 15], k=3

Goal: Find the 3rd smallest element in the array using a min heap

Step 1: Build min heap from array

Min heap array: [3, 7, 4, 10, 20, 15]

Why: Heap organizes elements so smallest is at the root for quick access

Step 2: Extract min (1st smallest): remove 3

Heap after removal: [4, 7, 15, 10, 20]

Why: Remove smallest element to move towards kth smallest

Step 3: Extract min (2nd smallest): remove 4

Heap after removal: [7, 10, 15, 20]

Why: Remove next smallest to approach kth smallest

Step 4: Extract min (3rd smallest): remove 7

Heap after removal: [10, 20, 15]

Why: The 3rd extracted element is the kth smallest

Result:

Heap after 3 extractions: [10, 20, 15]
Kth smallest element: 7

Annotated Code

DSA Go

package main

import (
	"container/heap"
	"fmt"
)

// IntHeap is a min-heap of ints
// Implements heap.Interface
// Len, Less, Swap, Push, Pop

type IntHeap []int

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

func (h *IntHeap) Push(x interface{}) {
	// add element to heap
	*h = append(*h, x.(int))
}

func (h *IntHeap) Pop() interface{} {
	// remove last element
	n := len(*h)
	x := (*h)[n-1]
	*h = (*h)[:n-1]
	return x
}

// kthSmallest returns the kth smallest element using a min heap
func kthSmallest(arr []int, k int) int {
	h := &IntHeap{}
	heap.Init(h) // organize heap before pushing elements
	// build heap from array
	for _, v := range arr {
		heap.Push(h, v) // add all elements
	}

	var kth int
	// extract min k times
	for i := 0; i < k; i++ {
		kth = heap.Pop(h).(int) // remove smallest
	}
	return kth
}

func main() {
	arr := []int{7, 10, 4, 3, 20, 15}
	k := 3
	result := kthSmallest(arr, k)
	fmt.Printf("%dth smallest element is %d\n", k, result)
}

for _, v := range arr { heap.Push(h, v) // add all elements }

Add all elements to the heap to prepare for extraction

heap.Init(h) // organize heap

Arrange elements so smallest is at the root

for i := 0; i < k; i++ { kth = heap.Pop(h).(int) // remove smallest }

Remove smallest element k times; last removed is kth smallest

Output

3th smallest element is 7

Complexity Analysis

Time: O(n + k log n) because building the heap takes O(n) and each of the k extractions takes O(log n)

Space: O(n) because the heap stores all n elements

vs Alternative: Sorting the array takes O(n log n), which is slower than building a heap and extracting k times when k is small

Edge Cases

k is 0 or less

Function returns 0 or invalid result since kth smallest does not exist

DSA Go

for i := 0; i < k; i++ {

k is greater than array length

Heap.Pop will panic or error because heap is empty before k pops

DSA Go

for i := 0; i < k; i++ {

array is empty

Heap is empty, Pop will panic or error

DSA Go

for i := 0; i < k; i++ {

When to Use This Pattern

When you need the kth smallest or largest element efficiently, especially if k is small compared to n, use a heap to avoid full sorting.

Common Mistakes

Mistake: Not building the heap properly before popping elements
Fix: Call heap.Init(h) after pushing all elements to organize the heap

Mistake: Popping fewer or more than k times
Fix: Pop exactly k times to get the kth smallest element

Summary

Finds the kth smallest element by building a min heap and extracting the smallest k times.

Use when you want kth smallest without sorting the entire array.

The smallest element is always at the root of the min heap, so popping k times gives the kth smallest.

Practice

1. What does a min heap help you find efficiently when looking for the kth smallest element in a list?

easy

A. The smallest elements in order

B. The largest elements in order

C. The middle element only

D. The sum of all elements

Solution

1. Step 1: Understand min heap property

   A min heap always keeps the smallest element at the top (root).

2. Step 2: Use min heap to find kth smallest

   By extracting the root k times, you get the kth smallest element.

3. Final Answer:

   The smallest elements in order -> Option A

4. Quick Check:

   Min heap = smallest elements first [OK]

Hint: Min heap root is always the smallest element [OK]

Common Mistakes:

• Confusing min heap with max heap
• Thinking min heap gives largest elements first
• Assuming kth smallest is the middle element

2. Which of the following Go code snippets correctly creates a min heap from a slice of integers nums using container/heap package?

easy

A. heap.Init(IntHeap(&nums))

B. heap.Init(nums)

C. heap.Init(&nums)

D. heap.Init(&IntHeap(nums))

Solution

1. Step 1: Understand heap.Init usage

   heap.Init requires a pointer to a type implementing heap.Interface.

2. Step 2: Convert slice to IntHeap and pass pointer

   We must convert nums to IntHeap and pass its pointer: &IntHeap(nums).

3. Final Answer:

   heap.Init(&IntHeap(nums)) -> Option D

4. Quick Check:

   heap.Init needs pointer to heap.Interface [OK]

Hint: Pass pointer to heap.Interface type for heap.Init [OK]

Common Mistakes:

• Passing slice directly without conversion
• Passing value instead of pointer
• Using wrong type conversion syntax

3. What is the output of the following Go code that finds the 3rd smallest element using a min heap?

package main

import (
  "container/heap"
  "fmt"
)

type IntHeap []int

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

func (h *IntHeap) Push(x interface{}) {
  *h = append(*h, x.(int))
}

func (h *IntHeap) Pop() interface{} {
  old := *h
  n := len(old)
  x := old[n-1]
  *h = old[0 : n-1]
  return x
}

func main() {
  nums := []int{7, 10, 4, 3, 20, 15}
  h := IntHeap(nums)
  heap.Init(&h)
  k := 3
  var kthSmallest int
  for i := 0; i < k; i++ {
    kthSmallest = heap.Pop(&h).(int)
  }
  fmt.Println(kthSmallest)
}

medium

A. 10

B. 7

C. 4

D. 3

Solution

1. Step 1: Build min heap from nums

   Heap after init: [3, 7, 4, 10, 20, 15] (smallest at root)

2. Step 2: Pop 3 times to get 3rd smallest

   Pop 1: 3, Pop 2: 4, Pop 3: 7

3. Final Answer:

   7 -> Option B

4. Quick Check:

   3rd smallest in [7,10,4,3,20,15] is 7 [OK]

Hint: Pop k times from min heap to get kth smallest [OK]

Common Mistakes:

• Not popping k times
• Confusing min heap with max heap
• Incorrect heap initialization

4. Identify the error in the following Go code snippet that tries to find the 2nd smallest element using a min heap:

nums := []int{5, 3, 8, 1}
h := IntHeap(nums)
heap.Init(h)
k := 2
for i := 0; i < k; i++ {
  val := heap.Pop(&h).(int)
  if i == k-1 {
    fmt.Println(val)
  }
}

medium

A. heap.Init should receive &h, not h

B. Pop should be called with h, not &h

C. k should be 3 to get 2nd smallest

D. nums slice should be sorted before heap.Init

Solution

1. Step 1: Check heap.Init argument

   heap.Init requires a pointer to the heap, so it should be heap.Init(&h).

2. Step 2: Confirm other calls are correct

   heap.Pop correctly uses &h, and k=2 is correct for 2nd smallest.

3. Final Answer:

   heap.Init should receive &h, not h -> Option A

4. Quick Check:

   heap.Init needs pointer to heap [OK]

Hint: Always pass pointer to heap in heap.Init [OK]

Common Mistakes:

• Passing value instead of pointer to heap.Init
• Confusing Pop argument
• Incorrect k value for kth smallest

5. Given a large unsorted array of integers, which approach is most efficient to find the 5th smallest element using heaps in Go? A) Build a min heap of all elements and pop 5 times. B) Build a max heap of size 5 and iterate through array. C) Sort the array and pick the 5th element. D) Use a min heap but pop all elements until the 5th smallest is found.

hard

A. Build a min heap of all elements and pop 5 times.

B. Sort the array and pick the 5th element.

C. Build a max heap of size 5 and iterate through array.

D. Use a min heap but pop all elements until the 5th smallest is found.

Solution

1. Step 1: Understand efficiency of building full min heap

   Building a min heap of all elements and popping 5 times is O(n + k log n), which can be costly for large n.

2. Step 2: Use max heap of size k for better efficiency

   Maintaining a max heap of size 5 while iterating keeps track of 5 smallest elements efficiently in O(n log k).

3. Step 3: Compare other options

   Sorting is O(n log n), popping all elements is inefficient, so max heap size k is best.

4. Final Answer:

   Build a max heap of size 5 and iterate through array. -> Option C

5. Quick Check:

   Max heap size k = efficient kth smallest [OK]

Hint: Use max heap of size k for kth smallest in large arrays [OK]

Common Mistakes:

• Building full min heap for large arrays
• Sorting entire array unnecessarily
• Popping all elements from min heap