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.