Median of Data Stream Using Two Heaps in DSA Go - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Median After Adding Numbers

What is the median after adding the numbers 5, 15, 1, 3 in order using two heaps?

DSA Go

package main

import (
	"container/heap"
	"fmt"
)

// IntHeap is a min-heap of ints.
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))
	heap.Fix(h, h.Len()-1)
}

func (h *IntHeap) Pop() interface{} {
	n := h.Len()
	x := (*h)[0]
	(*h)[0] = (*h)[n-1]
	*h = (*h)[:n-1]
	heap.Fix(h, 0)
	return x
}

// MaxHeap is a max-heap of ints (invert Less).
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))
	heap.Fix(h, h.Len()-1)
}

func (h *MaxHeap) Pop() interface{} {
	n := h.Len()
	x := (*h)[0]
	(*h)[0] = (*h)[n-1]
	*h = (*h)[:n-1]
	heap.Fix(h, 0)
	return x
}

func main() {
	low := &MaxHeap{}
	high := &IntHeap{}
	heap.Init(low)
	heap.Init(high)

	nums := []int{5, 15, 1, 3}
	for _, num := range nums {
		if low.Len() == 0 || num <= (*low)[0] {
			heap.Push(low, num)
		} else {
			heap.Push(high, num)
		}

		// Balance heaps
		if low.Len() > high.Len()+1 {
			val := heap.Pop(low).(int)
			heap.Push(high, val)
		} else if high.Len() > low.Len() {
			val := heap.Pop(high).(int)
			heap.Push(low, val)
		}

		// Calculate median
		var median float64
		if low.Len() == high.Len() {
			median = float64((*low)[0]+(*high)[0]) / 2.0
		} else {
			median = float64((*low)[0])
		}

		fmt.Printf("Median after adding %d: %.1f\n", num, median)
	}
}

A

Median after adding 5: 5.0
Median after adding 15: 15.0
Median after adding 1: 5.0
Median after adding 3: 3.0

B

Median after adding 5: 5.0
Median after adding 15: 15.0
Median after adding 1: 1.0
Median after adding 3: 4.0

C

Median after adding 5: 5.0
Median after adding 15: 10.0
Median after adding 1: 1.0
Median after adding 3: 3.0

D

Median after adding 5: 5.0
Median after adding 15: 10.0
Median after adding 1: 5.0
Median after adding 3: 4.0

💡 Hint

Balance the two heaps so their sizes differ by at most one. Median is top of max-heap or average of tops.

We add numbers one by one, pushing smaller half into max-heap and larger half into min-heap. Balancing ensures median is either top of max-heap or average of tops.

🧠 Conceptual

intermediate

Why Use Two Heaps for Median of Data Stream?

Why do we use two heaps (a max-heap and a min-heap) to find the median in a data stream?

A To keep the smaller half of numbers in max-heap and larger half in min-heap, so median is easily found at the top of heaps.

B To use heaps as queues for first-in-first-out order of numbers.

C To store all numbers in two heaps randomly for faster insertion.

D To sort all numbers in one heap and then pop the median directly.

💡 Hint

Think about how median splits data into two halves.

Two heaps split the data into smaller and larger halves. Max-heap stores smaller half so its top is the largest of smaller numbers. Min-heap stores larger half so its top is the smallest of larger numbers. Median is either top of max-heap or average of tops.

🔧 Debug

advanced

Identify the Bug in Median Calculation Code

What error will this code produce when calculating median after adding numbers using two heaps? Code snippet: if low.Len() == high.Len() { median = float64(((*low)[0] + (*high)[0]) / 2) } else { median = float64((*low)[0]) } Note: low is max-heap, high is min-heap.

A No error, code runs correctly and calculates median.

B Compilation error because integer division truncates before float conversion.

C Wrong median value because division by 2 should be 2.0 to get float.

D Runtime error due to accessing empty heap when one heap is empty.

💡 Hint

Check how division works between integers and floats in Go.

In Go, integer division truncates before converting to float64. Dividing by 2 (int) causes truncation. Dividing by 2.0 (float64) ensures correct float division.

❓ Predict Output

advanced

Output After Balancing Heaps

Given the sequence of numbers added: 10, 20, 30, 40, 50, what is the content of the max-heap (low) and min-heap (high) after all insertions and balancing?

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))
	heap.Fix(h, h.Len()-1)
}
func (h *IntHeap) Pop() interface{} {
	n := h.Len()
	x := (*h)[0]
	(*h)[0] = (*h)[n-1]
	*h = (*h)[:n-1]
	heap.Fix(h, 0)
	return x
}

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))
	heap.Fix(h, h.Len()-1)
}
func (h *MaxHeap) Pop() interface{} {
	n := h.Len()
	x := (*h)[0]
	(*h)[0] = (*h)[n-1]
	*h = (*h)[:n-1]
	heap.Fix(h, 0)
	return x
}

func main() {
	low := &MaxHeap{}
	high := &IntHeap{}
	heap.Init(low)
	heap.Init(high)

	nums := []int{10, 20, 30, 40, 50}
	for _, num := range nums {
		if low.Len() == 0 || num <= (*low)[0] {
			heap.Push(low, num)
		} else {
			heap.Push(high, num)
		}

		if low.Len() > high.Len()+1 {
			val := heap.Pop(low).(int)
			heap.Push(high, val)
		} else if high.Len() > low.Len() {
			val := heap.Pop(high).(int)
			heap.Push(low, val)
		}
	}

	fmt.Printf("Max-heap (low): %v\n", *low)
	fmt.Printf("Min-heap (high): %v\n", *high)
}

A

Max-heap (low): [30, 10, 20]
Min-heap (high): [40, 50]

B

Max-heap (low): [20, 10]
Min-heap (high): [30, 40, 50]

C

Max-heap (low): [50, 40, 30]
Min-heap (high): [20, 10]

D

Max-heap (low): [10, 20, 30]
Min-heap (high): [40, 50]

💡 Hint

Remember max-heap stores smaller half, min-heap stores larger half, and heaps are balanced in size.

After inserting all numbers and balancing, max-heap contains the smaller half [30, 10, 20] (max-heap order), min-heap contains larger half [40, 50].

🚀 Application

expert

Calculate Median After Complex Stream

Given the stream of numbers: 2, 8, 3, 5, 10, 9, 4, 7, 6, what is the median after all numbers are added using two heaps?

A 5.5

B 6.0

C 7.0

D 5.0

💡 Hint

Balance heaps after each insertion and find median from tops.

After adding all numbers and balancing heaps, the median is the middle value 6.0 because the total count is odd (9).