Kth Largest Element Using Max Heap in DSA Go - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Max Heap after inserting elements

What is the printed state of the max heap after inserting the elements [3, 1, 5, 12, 10] in that order?

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{} {
	n := len(*h)
	x := (*h)[n-1]
	*h = (*h)[:n-1]
	return x
}

func main() {
	h := &MaxHeap{}
	heap.Init(h)
	elements := []int{3, 1, 5, 12, 10}
	for _, v := range elements {
		heap.Push(h, v)
	}
	fmt.Println(*h)
}

A [10 12 5 3 1]

B [12 10 5 1 3]

C [12 10 5 3 1]

D [5 3 1 10 12]

💡 Hint

Remember that in a max heap, the largest element is at the root and the heap property is maintained after each insertion.

The max heap property ensures the largest element is at the root. After inserting 3,1,5,12,10, the heap array representation is [12 10 5 3 1].

❓ Predict Output

intermediate

Output after extracting max element from max heap

Given a max heap represented as [20, 15, 18, 8, 10, 5], what is the heap state after one Pop operation?

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{} {
	n := len(*h)
	x := (*h)[n-1]
	*h = (*h)[:n-1]
	return x
}

func main() {
	h := &MaxHeap{20, 15, 18, 8, 10, 5}
	heap.Init(h)
	heap.Pop(h)
	fmt.Println(*h)
}

A [15 10 5 8]

B [18 15 5 8 10]

C [15 18 10 8 5]

D [18 15 10 8 5]

💡 Hint

Pop removes the root (max) and then heapifies to maintain max heap property.

After popping 20, the heap reorders to maintain max heap property resulting in [18 15 10 8 5].

🧠 Conceptual

advanced

Understanding Kth Largest Element Extraction

If you want to find the 3rd largest element using a max heap built from an array, which of the following steps is correct?

A Build a max heap, then pop the max element 3 times; the last popped element is the 3rd largest.

B Build a max heap, then pop the max element once; the root is the 3rd largest.

C Build a max heap, then pop the max element 2 times; the next root is the 3rd largest.

D Build a max heap, then pop the max element 4 times; the last popped element is the 3rd largest.

💡 Hint

Think about how many times you remove the largest element to reach the kth largest.

Popping the max element k times removes the top k largest elements. The kth popped element is the kth largest.

🔧 Debug

advanced

Identify the error in Kth largest element code snippet

What error will this Go code produce when trying to find the 2nd largest element using a max heap?

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{} {
	n := len(*h)
	x := (*h)[n-1]
	*h = (*h)[:n-1]
	return x
}

func main() {
	h := &MaxHeap{10, 5, 20, 8}
	heap.Init(h)
	heap.Pop(h)
	next := (*h)[0]
	fmt.Println(next)
}

A Prints 10

B Prints 20

C Prints 5

D Runtime panic: index out of range

💡 Hint

Check the Less function for max heap property correctness.

Less function uses < which creates a min heap, so after popping max (which is actually min), the root is 10, not the max.

🚀 Application

expert

Find the 4th largest element using max heap operations

Given the array [7, 10, 4, 3, 20, 15], what is the 4th largest element after building a max heap and popping the max element 4 times?

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{} {
	n := len(*h)
	x := (*h)[n-1]
	*h = (*h)[:n-1]
	return x
}

func main() {
	h := &MaxHeap{}
	elements := []int{7, 10, 4, 3, 20, 15}
	for _, v := range elements {
		heap.Push(h, v)
	}
	heap.Init(h)
	var kthLargest int
	for i := 0; i < 4; i++ {
		kthLargest = heap.Pop(h).(int)
	}
	fmt.Println(kthLargest)
}

A 15

B 7

C 4

D 10

💡 Hint

Pop the max element 4 times and track the last popped value.

The popped elements in order are 20, 15, 10, 7. The 4th largest is 7.