Kth Smallest Element Using Min Heap in DSA Go - Build from Scratch

Kth Smallest Element Using Min Heap

📖 Scenario: You have a list of numbers representing the scores of players in a game. You want to find the kth smallest score to know who is just above the lowest scores.

🎯 Goal: Build a program that uses a min heap to find the kth smallest element in a list of integers.

📋 What You'll Learn

Create a slice called scores with the exact values: 7, 10, 4, 3, 20, 15

Create an integer variable called k and set it to 3

Use Go's container/heap package to build a min heap from scores

Pop elements from the min heap k-1 times to reach the kth smallest element

Print the kth smallest element

💡 Why This Matters

🌍 Real World

Finding the kth smallest or largest element is useful in ranking systems, statistics, and real-time data analysis where you want to quickly find thresholds or percentiles.

💼 Career

Understanding heaps and how to use them to find kth smallest or largest elements is a common task in software engineering interviews and is useful in roles involving data processing and algorithm optimization.

1

Create the initial data slice

Create a slice called scores with the exact values 7, 10, 4, 3, 20, 15.

DSA Go

# Create the slice scores with values 7, 10, 4, 3, 20, 15
# Your code here

Hint

Use scores := []int{7, 10, 4, 3, 20, 15} to create the slice.

2

Add the kth variable

Create an integer variable called k and set it to 3.

DSA Go

package main

func main() {
    scores := []int{7, 10, 4, 3, 20, 15}
    // Create variable k and set it to 3
    // Your code here
}

Hint

Use k := 3 to create the variable.

3

Build the min heap and find the kth smallest element

Import container/heap. Define a type IntHeap as a slice of ints that implements heap.Interface. Initialize h as IntHeap(scores). Use heap.Init(&h) to build the min heap. Pop elements from h k-1 times using heap.Pop(&h) to remove the smallest elements.

DSA Go

package main

import (
    "container/heap"
    "fmt"
)

// Define IntHeap type and methods here

func main() {
    scores := []int{7, 10, 4, 3, 20, 15}
    k := 3
    // Initialize min heap h from scores
    // Use heap.Init(&h)
    // Pop k-1 elements from h
    // Your code here
}

Hint

Define IntHeap with required methods to use container/heap. Initialize and pop k-1 times.

4

Print the kth smallest element

Print the kth smallest element by popping once more from h and printing the result using fmt.Println.

DSA Go

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() {
    scores := []int{7, 10, 4, 3, 20, 15}
    k := 3

    h := IntHeap(scores)
    heap.Init(&h)

    for i := 0; i < k-1; i++ {
        heap.Pop(&h)
    }
    // Print the kth smallest element
    // Your code here
}

Hint

Pop once more from h and print the value using fmt.Println.

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