Kth Largest Element Using Max Heap in DSA Go - Build from Scratch

Kth Largest Element Using Max Heap

📖 Scenario: You are working with a list of numbers representing daily sales amounts. Your manager wants to know the kth largest sale to understand the sales performance.

🎯 Goal: Build a Go program that uses a max heap to find the kth largest element in a list of sales numbers.

📋 What You'll Learn

Create a slice called sales with the exact values: 45, 12, 78, 34, 89, 23, 56

Create an integer variable called k and set it to 3

Build a max heap from the sales slice

Extract the maximum element from the heap k times to find the kth largest sale

Print the kth largest sale using fmt.Println

💡 Why This Matters

🌍 Real World

Finding the kth largest sale helps businesses understand their sales distribution and identify top-performing days.

💼 Career

Understanding heaps and selection algorithms is useful for roles in data analysis, software engineering, and any job involving efficient data processing.

1

Create the sales data slice

Create a slice called sales with these exact values: 45, 12, 78, 34, 89, 23, 56

DSA Go

package main

func main() {
    // Create the sales slice with the exact values
    // Your code here
}

Hint

Use sales := []int{45, 12, 78, 34, 89, 23, 56} to create the slice.

2

Set the kth position

Create an integer variable called k and set it to 3

DSA Go

package main

func main() {
    sales := []int{45, 12, 78, 34, 89, 23, 56}
    // Set k to 3
    // Your code here
}

Hint

Use k := 3 to set the kth largest position.

3

Build max heap and extract kth largest

Use the container/heap package to build a max heap from sales. Then extract the maximum element from the heap k times to find the kth largest sale. Store the kth largest sale in a variable called kthLargest.

DSA Go

package main

import (
    "container/heap"
    "fmt"
)

type MaxHeap []int

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

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

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

func main() {
    sales := []int{45, 12, 78, 34, 89, 23, 56}
    k := 3
    // Build max heap from sales
    // Extract max k times
    // Store kth largest in kthLargest
    // Your code here
}

Hint

Use heap.Init(&h) to build the heap. Use a for loop from 0 to k and pop the max element each time. Store the last popped value in kthLargest.

4

Print the kth largest sale

Print the variable kthLargest using fmt.Println(kthLargest)

DSA Go

package main

import (
    "container/heap"
    "fmt"
)

type MaxHeap []int

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

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

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

func main() {
    sales := []int{45, 12, 78, 34, 89, 23, 56}
    k := 3

    h := MaxHeap(sales)
    heap.Init(&h)

    var kthLargest int
    for i := 0; i < k; i++ {
        kthLargest = heap.Pop(&h).(int)
    }
    // Print kthLargest
    // Your code here
}

Hint

Use fmt.Println(kthLargest) to print the kth largest sale.