Median of Data Stream Using Two Heaps in DSA Go - Build from Scratch

Median of Data Stream Using Two Heaps

📖 Scenario: Imagine you are building a system that receives a continuous stream of numbers, like temperatures from sensors. You want to quickly find the middle value (median) of all numbers received so far at any time.

🎯 Goal: Build a program in Go that uses two heaps (a max heap and a min heap) to efficiently find the median of a stream of numbers as they arrive.

📋 What You'll Learn

Create two heaps: a max heap for the lower half of numbers and a min heap for the upper half.

Add numbers to the heaps while keeping their sizes balanced.

Calculate the median based on the sizes and top elements of the heaps.

Print the median after inserting each number.

💡 Why This Matters

🌍 Real World

Finding the median in real-time data streams like sensor readings, stock prices, or user ratings.

💼 Career

This technique is useful for software engineers working on data processing, real-time analytics, or financial applications.

1

Create two heaps for storing numbers

Create two variables called low and high as slices of integers. These will represent the max heap and min heap respectively.

DSA Go

var low []int
var high []int
// Your code here

Hint

Use slices to represent heaps initially. We will add heap operations later.

2

Add a helper function to balance the heaps

Add a function called balanceHeaps that keeps the size difference between low and high at most 1 by moving elements between them.

DSA Go

package main

import "fmt"

var low []int
var high []int

func balanceHeaps() {
    // Your code here
}

func main() {
    // Your code here
}

Hint

Check the lengths of both slices and move the last element from the bigger heap to the smaller heap.

3

Add numbers and maintain heap properties

Add a function called addNumber that takes an integer num. If low is empty or num is less than or equal to the last element of low, append num to low. Otherwise, append it to high. Then call balanceHeaps().

DSA Go

package main

import "fmt"

var low []int
var high []int

func balanceHeaps() {
    if len(low) > len(high)+1 {
        high = append(high, low[len(low)-1])
        low = low[:len(low)-1]
    } else if len(high) > len(low)+1 {
        low = append(low, high[len(high)-1])
        high = high[:len(high)-1]
    }
}

func addNumber(num int) {
    // Your code here
}

func main() {
    // Your code here
}

Hint

Compare num with the last element of low to decide where to add it.

4

Print the median after each insertion

In main, add these numbers in order: 5, 15, 1, 3 by calling addNumber. After each addition, print the median. If low and high have the same length, print the average of their last elements as a float. Otherwise, print the last element of the bigger heap as a float.

DSA Go

package main

import "fmt"

var low []int
var high []int

func balanceHeaps() {
    if len(low) > len(high)+1 {
        high = append(high, low[len(low)-1])
        low = low[:len(low)-1]
    } else if len(high) > len(low)+1 {
        low = append(low, high[len(high)-1])
        high = high[:len(high)-1]
    }
}

func addNumber(num int) {
    if len(low) == 0 || num <= low[len(low)-1] {
        low = append(low, num)
    } else {
        high = append(high, num)
    }
    balanceHeaps()
}

func main() {
    addNumber(5)
    // Your code here
}

Hint

After each addNumber call, check the sizes of low and high and print the median accordingly.