Median of Data Stream Using Two Heaps in DSA C

Mental Model

Keep the smaller half of numbers in a max heap and the larger half in a min heap to quickly find the middle value.

Analogy: Imagine two boxes: one holds all the smaller numbers and the other holds all the bigger numbers. The middle number is at the edge between these two boxes.

Max Heap (smaller half): 10 7 5
Min Heap (larger half): 12 15 20
Median is between the top of max heap and min heap.

Dry Run Walkthrough

Input: Stream: 5, 15, 1, 3

Goal: Find the median after each number is added

Step 1: Add 5 to max heap

Max Heap: 5
Min Heap: empty

Why: Start by adding the first number to max heap

Step 2: Add 15 to min heap

Max Heap: 5
Min Heap: 15

Why: Add next number to min heap because it is greater than max heap top

Step 3: Add 1 to max heap and rebalance

Max Heap: 5, 1
Min Heap: 15

Why: Add smaller number to max heap to keep halves balanced

Step 4: Add 3 to max heap, then move top from max heap to min heap to rebalance

Max Heap: 3, 1
Min Heap: 5, 15

Why: Rebalance heaps to keep size difference at most 1

Result:

Median after each insertion:
After 5: 5
After 15: 10 (average of 5 and 15)
After 1: 5
After 3: 4 (average of 3 and 5)

Annotated Code

DSA C

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

// Max Heap structure
typedef struct {
    int *arr;
    int size;
    int capacity;
} MaxHeap;

// Min Heap structure
typedef struct {
    int *arr;
    int size;
    int capacity;
} MinHeap;

// Function prototypes
MaxHeap* createMaxHeap(int capacity);
MinHeap* createMinHeap(int capacity);
void maxHeapInsert(MaxHeap* heap, int val);
void minHeapInsert(MinHeap* heap, int val);
int maxHeapExtract(MaxHeap* heap);
int minHeapExtract(MinHeap* heap);
int maxHeapTop(MaxHeap* heap);
int minHeapTop(MinHeap* heap);
void maxHeapifyUp(MaxHeap* heap, int index);
void maxHeapifyDown(MaxHeap* heap, int index);
void minHeapifyUp(MinHeap* heap, int index);
void minHeapifyDown(MinHeap* heap, int index);

// MedianFinder structure
typedef struct {
    MaxHeap* maxHeap; // smaller half
    MinHeap* minHeap; // larger half
} MedianFinder;

MedianFinder* medianFinderCreate(int capacity) {
    MedianFinder* mf = (MedianFinder*)malloc(sizeof(MedianFinder));
    mf->maxHeap = createMaxHeap(capacity);
    mf->minHeap = createMinHeap(capacity);
    return mf;
}

void medianFinderAddNum(MedianFinder* mf, int num) {
    if (mf->maxHeap->size == 0 || num <= maxHeapTop(mf->maxHeap)) {
        maxHeapInsert(mf->maxHeap, num); // add to smaller half
    } else {
        minHeapInsert(mf->minHeap, num); // add to larger half
    }

    // Rebalance heaps if size difference > 1
    if (mf->maxHeap->size > mf->minHeap->size + 1) {
        int val = maxHeapExtract(mf->maxHeap);
        minHeapInsert(mf->minHeap, val);
    } else if (mf->minHeap->size > mf->maxHeap->size + 1) {
        int val = minHeapExtract(mf->minHeap);
        maxHeapInsert(mf->maxHeap, val);
    }
}

double medianFinderFindMedian(MedianFinder* mf) {
    if (mf->maxHeap->size > mf->minHeap->size) {
        return (double)maxHeapTop(mf->maxHeap);
    } else if (mf->minHeap->size > mf->maxHeap->size) {
        return (double)minHeapTop(mf->minHeap);
    } else {
        return ((double)maxHeapTop(mf->maxHeap) + (double)minHeapTop(mf->minHeap)) / 2.0;
    }
}

// Max Heap functions
MaxHeap* createMaxHeap(int capacity) {
    MaxHeap* heap = (MaxHeap*)malloc(sizeof(MaxHeap));
    heap->arr = (int*)malloc(sizeof(int) * capacity);
    heap->size = 0;
    heap->capacity = capacity;
    return heap;
}

void maxHeapInsert(MaxHeap* heap, int val) {
    heap->arr[heap->size] = val;
    heap->size++;
    maxHeapifyUp(heap, heap->size - 1);
}

int maxHeapExtract(MaxHeap* heap) {
    int top = heap->arr[0];
    heap->arr[0] = heap->arr[heap->size - 1];
    heap->size--;
    maxHeapifyDown(heap, 0);
    return top;
}

int maxHeapTop(MaxHeap* heap) {
    return heap->arr[0];
}

void maxHeapifyUp(MaxHeap* heap, int index) {
    while (index > 0) {
        int parent = (index - 1) / 2;
        if (heap->arr[parent] >= heap->arr[index]) break;
        int temp = heap->arr[parent];
        heap->arr[parent] = heap->arr[index];
        heap->arr[index] = temp;
        index = parent;
    }
}

void maxHeapifyDown(MaxHeap* heap, int index) {
    int left, right, largest;
    while (1) {
        left = 2 * index + 1;
        right = 2 * index + 2;
        largest = index;
        if (left < heap->size && heap->arr[left] > heap->arr[largest]) largest = left;
        if (right < heap->size && heap->arr[right] > heap->arr[largest]) largest = right;
        if (largest == index) break;
        int temp = heap->arr[index];
        heap->arr[index] = heap->arr[largest];
        heap->arr[largest] = temp;
        index = largest;
    }
}

// Min Heap functions
MinHeap* createMinHeap(int capacity) {
    MinHeap* heap = (MinHeap*)malloc(sizeof(MinHeap));
    heap->arr = (int*)malloc(sizeof(int) * capacity);
    heap->size = 0;
    heap->capacity = capacity;
    return heap;
}

void minHeapInsert(MinHeap* heap, int val) {
    heap->arr[heap->size] = val;
    heap->size++;
    minHeapifyUp(heap, heap->size - 1);
}

int minHeapExtract(MinHeap* heap) {
    int top = heap->arr[0];
    heap->arr[0] = heap->arr[heap->size - 1];
    heap->size--;
    minHeapifyDown(heap, 0);
    return top;
}

int minHeapTop(MinHeap* heap) {
    return heap->arr[0];
}

void minHeapifyUp(MinHeap* heap, int index) {
    while (index > 0) {
        int parent = (index - 1) / 2;
        if (heap->arr[parent] <= heap->arr[index]) break;
        int temp = heap->arr[parent];
        heap->arr[parent] = heap->arr[index];
        heap->arr[index] = temp;
        index = parent;
    }
}

void minHeapifyDown(MinHeap* heap, int index) {
    int left, right, smallest;
    while (1) {
        left = 2 * index + 1;
        right = 2 * index + 2;
        smallest = index;
        if (left < heap->size && heap->arr[left] < heap->arr[smallest]) smallest = left;
        if (right < heap->size && heap->arr[right] < heap->arr[smallest]) smallest = right;
        if (smallest == index) break;
        int temp = heap->arr[index];
        heap->arr[index] = heap->arr[smallest];
        heap->arr[smallest] = temp;
        index = smallest;
    }
}

int main() {
    int stream[] = {5, 15, 1, 3};
    int n = sizeof(stream) / sizeof(stream[0]);
    MedianFinder* mf = medianFinderCreate(n);

    for (int i = 0; i < n; i++) {
        medianFinderAddNum(mf, stream[i]);
        double median = medianFinderFindMedian(mf);
        printf("After inserting %d, median is %.1f\n", stream[i], median);
    }

    return 0;
}

if (mf->maxHeap->size == 0 || num <= maxHeapTop(mf->maxHeap)) {

decide which heap to add the new number to keep halves balanced

maxHeapInsert(mf->maxHeap, num);

add number to max heap (smaller half)

minHeapInsert(mf->minHeap, num);

add number to min heap (larger half)

if (mf->maxHeap->size > mf->minHeap->size + 1) {

check if max heap is too big and rebalance

int val = maxHeapExtract(mf->maxHeap);

remove top from max heap to move to min heap

minHeapInsert(mf->minHeap, val);

insert extracted value into min heap

else if (mf->minHeap->size > mf->maxHeap->size + 1) {

check if min heap is too big and rebalance

int val = minHeapExtract(mf->minHeap);

remove top from min heap to move to max heap

maxHeapInsert(mf->maxHeap, val);

insert extracted value into max heap

if (mf->maxHeap->size > mf->minHeap->size) {

if max heap bigger, median is top of max heap

else if (mf->minHeap->size > mf->maxHeap->size) {

if min heap bigger, median is top of min heap

else {

if equal size, median is average of tops

Output

After inserting 5, median is 5.0

After inserting 15, median is 10.0

After inserting 1, median is 5.0

After inserting 3, median is 4.0

Complexity Analysis

Time: O(log n) per insertion because each insert and rebalance involves heap operations that take log n time

Space: O(n) because all numbers are stored in the two heaps

vs Alternative: Compared to sorting the entire stream after each insertion (O(n log n)), this approach is faster for continuous median queries

Edge Cases

empty stream

median query returns no value or zero since no numbers are added

DSA C

if (mf->maxHeap->size == 0 || num <= maxHeapTop(mf->maxHeap)) {

all numbers equal

heaps balance evenly and median is that number

DSA C

if (mf->maxHeap->size > mf->minHeap->size) {

stream with one element

median is that single element

DSA C

if (mf->maxHeap->size == 0 || num <= maxHeapTop(mf->maxHeap)) {

When to Use This Pattern

When you need to find the median of a stream of numbers efficiently, use two heaps to keep track of the smaller and larger halves for quick median retrieval.

Common Mistakes

Mistake: Not rebalancing heaps after insertion causing size difference greater than 1
Fix: Always check and rebalance heaps after each insertion to maintain size difference at most 1

Mistake: Adding all numbers to one heap only
Fix: Distribute numbers between max heap and min heap based on their value relative to current median

Summary

It finds the median of a stream by keeping two heaps for smaller and larger halves.

Use it when you want to get the median quickly after each new number in a stream.

The key is balancing two heaps so the median is always at the top of one or average of both.

Practice

1. What is the main purpose of using two heaps (a max-heap and a min-heap) to find the median of a data stream?

easy

A. To store all numbers in a single data structure

B. To sort all numbers in ascending order

C. To remove duplicate numbers from the stream

D. To efficiently keep track of the lower half and upper half of the numbers separately

Solution

1. Step 1: Understand the role of two heaps

   The max-heap stores the smaller half of the numbers, and the min-heap stores the larger half.

2. Step 2: Explain how this helps find the median

   By balancing these heaps, the median is either the top of one heap or the average of the tops of both heaps.

3. Final Answer:

   To efficiently keep track of the lower half and upper half of the numbers separately -> Option D

4. Quick Check:

   Two heaps split data halves = To efficiently keep track of the lower half and upper half of the numbers separately [OK]

Hint: Two heaps split data halves for quick median [OK]

Common Mistakes:

• Thinking heaps sort all data fully
• Using one heap only
• Confusing heaps with arrays

2. Which of the following is the correct way to insert a new number into the two heaps when maintaining the median?

easy

A. Insert into the heap based on comparison with max-heap top

B. Insert into min-heap only

C. Insert into max-heap only

D. Always insert into min-heap first, then balance heaps

Solution

1. Step 1: Decide where to insert the new number

   If the new number is less than or equal to the max-heap top, insert into max-heap; otherwise, insert into min-heap.

2. Step 2: Balance the heaps if needed

   After insertion, balance the heaps so their sizes differ by at most one.

3. Final Answer:

   Insert into the heap based on comparison with max-heap top -> Option A

4. Quick Check:

   Compare with max-heap top to choose heap [OK]

Hint: Compare new number with max-heap top to choose heap [OK]

Common Mistakes:

• Always inserting into one heap without condition
• Not balancing heaps after insertion
• Inserting into wrong heap based on min-heap top

3. Consider the following sequence of numbers inserted into the data stream: 5, 15, 1, 3. What is the median after all insertions using two heaps?

Insert 5
Insert 15
Insert 1
Insert 3
Find median

medium

A. 5

B. 3

C. 4

D. 6

Solution

1. Step 1: Insert numbers and balance heaps

   Insert 5 into max-heap ([5]); insert 15 into min-heap ([15]); insert 1 (<=5) into max-heap ([5,1] top=5); insert 3 (<=5) into max-heap ([5,3,1] top=5), sizes 3 vs 1, balance: min.push(5) ([15,5] top=5), max.pop() ([3,1] top=3).

2. Step 2: Calculate median from heaps

   Heaps sizes equal (2 and 2), median = average of max-heap top (3) and min-heap top (5) = (3+5)/2 = 4.

3. Final Answer:

   4 -> Option C

4. Quick Check:

   Median of [1,3,5,15] = 4 [OK]

Hint: Median is average when heaps equal size [OK]

Common Mistakes:

• Taking median as max-heap top only
• Not balancing heaps after insertions
• Calculating median incorrectly as 5 or 3

4. The following code snippet tries to maintain median using two heaps but has a bug. What is the bug?

void addNumber(int num, priority_queue<int>& maxHeap, priority_queue& minHeap) {
    if (maxHeap.empty() || num <= maxHeap.top()) {
        maxHeap.push(num);
    } else {
        minHeap.push(num);
    }
    if (maxHeap.size() > minHeap.size() + 1) {
        minHeap.push(maxHeap.top());
        maxHeap.pop();
    } else if (minHeap.size() > maxHeap.size() + 1) {
        maxHeap.push(minHeap.top());
        minHeap.pop();
    }
}

medium

A. The balancing pops top element before pushing, causing wrong order

B. The condition to insert into maxHeap is incorrect

C. The heaps are not balanced after insertion

D. The function does not return the median

Solution

1. Step 1: Analyze balancing logic

   When balancing, the code pops the top element of one heap before pushing the new top to the other, which moves the wrong element.

2. Step 2: Explain correct balancing

   Correct approach is to push heap.top() first, then pop() to transfer the correct top element.

3. Final Answer:

   The balancing pops top element before pushing, causing wrong order -> Option A

4. Quick Check:

   Push top before pop to balance heaps correctly [OK]

Hint: Push top before pop when balancing heaps [OK]

Common Mistakes:

• Popping before pushing the correct top
• Ignoring heap size difference conditions
• Not handling empty heaps properly

5. You have a data stream of integers and want to find the median after each insertion. Using two heaps, how would you handle the case when the total number of elements is odd?

hard

A. The median is always the top of the min-heap

B. The median is the top element of the heap with one extra element

C. The median is always the top of the max-heap

D. The median is the average of the tops of both heaps

Solution

1. Step 1: Understand heap size difference

   When total elements are odd, one heap will have one more element than the other.

2. Step 2: Determine median from heaps

   The median is the top element of the heap that has the extra element, because it holds the middle value.

3. Final Answer:

   The median is the top element of the heap with one extra element -> Option B

4. Quick Check:

   Odd count median = top of larger heap [OK]

Hint: Median is top of bigger heap when odd count [OK]

Common Mistakes:

• Averaging tops when count is odd
• Assuming max-heap always has extra element
• Ignoring heap size difference