Sliding window median with two heaps

Why this matters

A monitoring tool receives one response time every second and shows the median response time over the last 60 seconds. The window moves forward with each new reading, so the oldest reading leaves as the newest one arrives. The tool must update the median after every reading without sorting the last 60 values each time.

This problem is a sliding window median. It is harder than the sliding window maximum that many courses teach first, because a median needs the whole sorted order of the window, not one extreme value. Two heaps solve it cleanly. One heap keeps the smaller half of the window, another keeps the larger half, and the median sits at the boundary between them.

The solution has one tricky part. A heap can remove its top value cheaply, but it cannot remove a value from the middle. When a value leaves the window, it may be buried inside a heap. The lesson shows a method called lazy deletion that handles this.

The previous lesson in this module used a min heap to track busy rooms. This lesson uses two heaps at once, and it does not repeat the basic heap operations.

Words used in this lesson

• Window: a block of consecutive numbers in a list. A window of size k holds exactly k numbers. As the window slides one step to the right, one number enters at the right end and one number leaves at the left end.
• Median: the middle value when the numbers are sorted. For an odd count, it is the middle number. For an even count, it is the average of the two middle numbers.
• Max heap: a heap whose top is the largest value. In C++ this is the default std::priority_queue<int>.
• Min heap: a heap whose top is the smallest value. In C++ it is std::priority_queue<int, std::vector<int>, std::greater<int>>.
• Lazy deletion: a way to remove a value from a heap later. You write down that the value should go away, and you actually drop it only when it reaches the top of the heap.

The median from sorted order

Take the window 3, 1, 2. Sorted, it is 1, 2, 3. The median is 2, the middle number. Now take the window 4, 1, 3, 2. Sorted, it is 1, 2, 3, 4. The two middle numbers are 2 and 3, so the median is their average, 2.5.

Here is the key picture. Split the sorted window into a lower half and an upper half.

• For 1, 2, 3, the lower half is 1 and the upper half is 3, with 2 in the middle. Put the middle value in the lower half, so the lower half has 2 values and the upper half has 1.
• For 1, 2, 3, 4, the lower half is 1, 2 and the upper half is 3, 4.

The median is then one of two things. For an odd window, it is the largest value of the lower half. For an even window, it is the average of the largest value of the lower half and the smallest value of the upper half.

So if you can always find the largest value of the lower half and the smallest value of the upper half, you have the median. Those two values are exactly what a max heap and a min heap give at their tops.

The idea: two heaps

Keep two heaps.

• low is a max heap with the smaller half of the window. Its top is the largest value in the lower half.
• high is a min heap with the larger half of the window. Its top is the smallest value in the upper half.

Two rules keep the structure correct.

1. Every value in low is at most every value in high. This keeps the halves in order.
2. The sizes differ by at most one. low may have one more value than high, but never two more, and high never has more than low.

When both rules hold, the median is easy. If low has one more value, the median is low.top(). If both have the same size, the median is the average of low.top() and high.top().

Worked example 1: a window of three

Use the list 1, 3, -1, -3, 5 with window size 3. The first window is 1, 3, -1, and the second is 3, -1, -3. Here is what happens in the first window.

• Insert 1. The low heap is empty, so 1 goes into low. Now low is {1} and high is empty. The sizes are 1 and 0, which is allowed.
• Insert 3. The top of low is 1, and 3 is not at most 1, so 3 goes into high. Now low is {1} and high is {3}. The sizes are 1 and 1, which is allowed.
• Insert -1. The top of low is 1, and -1 is at most 1, so -1 goes into low. Now low is {-1, 1} and high is {3}. The sizes are 2 and 1, which is allowed.

The window 1, 3, -1 has median 1. The top of low is 1, and low has one more value than high, so the median is low.top().

Now slide the window. Remove the value 1, which is the oldest value, and insert -3. Removing 1 is the hard part, because 1 sits in low but not at the top. The section on lazy deletion below handles that. Once 1 is gone, low is {-1} and high is {3}. Insert -3. The top of low is -1, and -3 is at most -1, so -3 goes into low. Now low is {-3, -1} and high is {3}. The sizes are 2 and 1, which is allowed, because low may have one more value than high. The median is the top of low, which is -1. The window 3, -1, -3 sorted is -3, -1, 3, and its median is -1. The answer matches, and no value had to move between the heaps.

The point of the example is the rule for moving values. After each change, check the two sizes. If low has two more values than high, or high has more values than low, move one top across to fix it. Otherwise leave the heaps alone.

Removing values: lazy deletion

A max heap or a min heap can remove its top in about log k steps. It cannot remove a value from the middle without a full search, and std::priority_queue has no remove function at all.

Lazy deletion solves this. When a value leaves the window, write it down in a count table called pending, which maps each value to the number of copies that should be removed. Do not touch the heaps yet. Then, whenever the top of a heap is a value with a pending count above zero, pop it and reduce the count. Each value is dropped only when it reaches the top, and that is cheap.

Here is why this is safe. Suppose the value 1 is in low but not at the top, and it has a pending count of 1. Nothing looks at it while it is buried, because the median only reads the tops. Later, when the values above it are popped or moved, 1 reaches the top. The code sees the pending count, pops it, and the count goes to zero. From that point the heap is correct again.

There is one more rule. The tops must be clean before the code reads them. So after each change, the code removes pending values from the top of both heaps. This is why the code below calls pruneLow and pruneHigh inside rebalance.

The full program

This program is a class RunningMedian that supports insert, erase and median, plus a function windowMedians that slides a window across a list. It prints the medians of the windows of the first example.

#include <algorithm>
#include <cstddef>
#include <functional>
#include <iomanip>
#include <iostream>
#include <queue>
#include <unordered_map>
#include <vector>
 
// Keeps the median of a multiset of ints that supports insert and erase.
class RunningMedian {
public:
    void insert(int x) {
        if (low_.empty() || x <= low_.top()) {
            low_.push(x);
            ++lowSize_;
        } else {
            high_.push(x);
            ++highSize_;
        }
        rebalance();
    }
 
    void erase(int x) {
        ++pending_[x];  // mark x as removed; the heap copy is dropped later
        if (x <= low_.top()) {
            --lowSize_;
        } else {
            --highSize_;
        }
        rebalance();
    }
 
    double median() const {
        if (lowSize_ > highSize_) {
            return low_.top();
        }
        return (static_cast<double>(low_.top()) + high_.top()) / 2.0;
    }
 
private:
    // low_ is a max heap holding the smaller half, high_ a min heap holding the larger half.
    std::priority_queue<int> low_;
    std::priority_queue<int, std::vector<int>, std::greater<int>> high_;
    std::unordered_map<int, int> pending_;  // value -> copies still waiting to be dropped
    std::size_t lowSize_ = 0;               // live values in low_
    std::size_t highSize_ = 0;              // live values in high_
 
    void pruneLow() {
        while (!low_.empty() && pending_[low_.top()] > 0) {
            --pending_[low_.top()];
            low_.pop();
        }
    }
 
    void pruneHigh() {
        while (!high_.empty() && pending_[high_.top()] > 0) {
            --pending_[high_.top()];
            high_.pop();
        }
    }
 
    void rebalance() {
        pruneLow();
        pruneHigh();
        if (lowSize_ > highSize_ + 1) {
            high_.push(low_.top());
            low_.pop();
            --lowSize_;
            ++highSize_;
            pruneLow();
        } else if (lowSize_ < highSize_) {
            low_.push(high_.top());
            high_.pop();
            ++lowSize_;
            --highSize_;
            pruneHigh();
        }
        pruneLow();
        pruneHigh();
    }
};
 
std::vector<double> windowMedians(const std::vector<int>& nums, std::size_t k) {
    RunningMedian rm;
    std::vector<double> result;
    for (std::size_t i = 0; i < nums.size(); ++i) {
        rm.insert(nums[i]);
        if (i >= k) {
            rm.erase(nums[i - k]);  // the value that just left the window
        }
        if (i + 1 >= k) {
            result.push_back(rm.median());
        }
    }
    return result;
}
 
int main() {
    std::vector<int> nums = {1, 3, -1, -3, 5, 3, 6, 7};
    std::cout << std::fixed << std::setprecision(1);
    for (double m : windowMedians(nums, 3)) {
        std::cout << m << ' ';
    }
    std::cout << '\n';
}

Compile and run it with:

g++ -std=c++20 -Wall -o median median.cpp
./median

Output:

1.0 -1.0 -1.0 3.0 5.0 6.0 

Each number is the median of one window of three: 1, 3, -1 gives 1.0, 3, -1, -3 gives -1.0, -1, -3, 5 gives -1.0, -3, 5, 3 gives 3.0, 5, 3, 6 gives 5.0, and 3, 6, 7 gives 6.0. A brute force check that sorts each window gives the same six values.

Three details in the code matter.

• pending_[x] is an unordered_map from value to count. The [] operator creates an entry with count 0 the first time a value is read, which is fine here.
• erase decides which heap the value is in by comparing with low_.top(). The top is already clean, because rebalance pruned it after the last change. A value at most the top of low belongs in low.
• rebalance ends with two prunes. The next insert or median call compares against the tops, so they must be live values.

Worked example 2: an even window

Use the list 1, 2, 3, 4, 5, 6 with window size 4. There are three windows: 1, 2, 3, 4, 2, 3, 4, 5, and 3, 4, 5, 6.

For the first window, the sorted order is 1, 2, 3, 4. The lower half is 1, 2 and the upper half is 3, 4. So low is {1, 2} with top 2, and high is {3, 4} with top 3. The sizes are equal, so the median is the average, (2 + 3) / 2 = 2.5.

Now slide to 2, 3, 4, 5. The value 1 leaves and 5 enters. Insert 5. The top of low is 2, and 5 is larger, so 5 goes into high. Now high has three values, 3, 4, 5, and low has two. The sizes are 2 and 3, which is not allowed, because high has more values than low. Move the top of high, which is 3, into low. Now low is {1, 2, 3}, but 1 has left the window. Erase 1 with lazy deletion. The live values are 2, 3 in low and 4, 5 in high. The median is (3 + 4) / 2 = 3.5, which matches the sorted window 2, 3, 4, 5.

A test that calls windowMedians on this list with window size 4 prints:

2.5 3.5 4.5 

Both halves of an even window are needed for the median. That is why the average of two tops appears in median(). The C++ code uses static_cast<double> before the addition, so the sum is a double and the division keeps the fraction. The mistakes section shows what happens without it.

Worked example 3: duplicates

Duplicate values are the case where a sliding window median most often goes wrong. Use the list 4, 1, 4, 1 with window size 2. The windows are 4, 1, 1, 4 and 4, 1. Each window has the two values 1 and 4, so each median is (1 + 4) / 2 = 2.5.

Duplicates also show up when a value leaves the window while another copy of it stays. Use the list 2, 2, 2, 9, 2, 2 with window size 3. The windows are 2, 2, 2, 2, 2, 9, 2, 9, 2, and 9, 2, 2. Their medians are all 2.

When the value 2 leaves the window, the code adds one pending count for 2. Some copies of 2 remain in the heaps, and the pending count removes only the copies that reach the top. Because all copies are the same number, it does not matter which copy is removed. The count of live values is what the median uses. A test that calls windowMedians on this list with window size 3 prints:

2.0 2.0 2.0 2.0 

This shows that the pending count is a count of values, not of heap positions.

How fast is it?

Each insert or erase changes the sizes of the heaps by one or two values, and it moves at most one value between the heaps. Each push or pop costs about log k, where k is the window size. So each step of the sliding window costs about log k.

Lazy deletion adds a small cost. A value stays in a heap after it leaves the window, until it reaches the top. The heaps can therefore hold more values than the window, but no more than the number of values that have entered the window, so memory stays about n, where n is the length of the list. Each value is removed from a heap at most once, so the total work for removals is also about n log k.

The whole sliding window costs about n log k steps for a list of n values, which is much better than sorting each window, which costs about n k log k.

Common mistakes

Dividing integers for an even window

For an even window, the median is the average of two numbers. If both numbers are int, the division truncates the fraction. The first two numbers in the list 1, 2 give this result:

int average of 1 and 2: 1
double average of 1 and 2: 1.5

The answer should be 1.5, so the code must convert at least one operand to double before dividing. The lesson's code does this with static_cast<double>(low_.top()).

Forgetting to remove values from the top

If erase marks a value as pending but the code never pops pending values from the tops, the removed values stay in the median. Here is the same window median logic with that step missing, on the first example:

1.0 -1.0 -1.0 1.0 3.0 3.0

The correct output is 1.0 -1.0 -1.0 3.0 5.0 6.0. The fourth window -3, 5, 3 has median 3, but the wrong version reports 1 because a value that already left the window is still counted. The fix is to prune both heap tops after every change, as rebalance does.

Calling a non-const function inside a const method

median() is marked const in the lesson's code, because reading the median does not change the sizes. If you try to call a pruning function from inside median(), g++ refuses. Here is a small program that shows the same error:

#include <queue>
 
struct Queue {
    std::priority_queue<int> q;
    void prune() { q.pop(); }
    int peek() const {
        prune();  // error: prune is not const
        return q.top();
    }
};
 
int main() {
    Queue x;
    return x.peek();
}

g++ reports:

snippet.cpp:7:14: error: passing ‘const Queue’ as ‘this’ argument discards qualifiers [-fpermissive]

The fix is to make the function that changes the heap non-const, and call it from rebalance or from insert and erase, which are not const. Keep median() const, and let it read the tops only after the last change has been pruned.

Using the wrong element to erase

The value that leaves the window is nums[i - k], not nums[i]. The element nums[i] has just entered the window, so erasing it would remove the new value and keep the old one. The median would then describe a different window. The fix is to check the index in the loop: erase only when i >= k, and erase nums[i - k].

Practice

Exercise 1: small window by hand

Find the median of each window of size 2 in the list 5, 15, 1, 3.

Show the answer.

The windows are 5, 15, 15, 1, and 1, 3. Their medians are (5 + 15) / 2 = 10, (1 + 15) / 2 = 8, and (1 + 3) / 2 = 2. Putting this list into main prints 10.0 8.0 2.0.

Exercise 2: window size one

Predict the output of windowMedians on 7, 2, 9 with window size 1.

Show the answer.

A window of size 1 holds one value, so each median is that value. The output is 7.0 2.0 9.0. In the code, each step inserts a new value and erases the previous one, so the window is always only the newest value.

Exercise 3: the whole list as one window

Predict the output of windowMedians on 1, 2, 3, 4, 5 with window size 5.

Show the answer.

There is one window, the whole list. Its sorted order is 1, 2, 3, 4, 5, and the median is 3. The output is 3.0.

Exercise 4: where does the median live

For an odd window, median() returns low_.top(), and for an even window it returns the average of the two tops. Explain why low_.top() must be the largest value in the lower half, not the smallest.

Show the answer.

The median of an odd window is the middle value. The lower half holds the smaller values, and its largest value is the one just below the middle. In the window 1, 2, 3, the lower half holds the two smallest values, 1 and 2. Its top is the largest of them, which is 2, the middle value. A min heap would have 1 at the top, which is not the median. That is why low_ is a max heap.

Exercise 5: a mixed list

Find the median of each window of size 3 in the list 10, 1, 9, 2, 8, and then check your answer by putting this list into main and running the program.

Show the answer.

The windows are 10, 1, 9, 1, 9, 2, and 9, 2, 8. Sorted, they are 1, 9, 10 with median 9, 1, 2, 9 with median 2, and 2, 8, 9 with median 8. The output is 9.0 2.0 8.0.

Summary

• A sliding window median is the middle of the window's sorted values, and it can be read from the boundary between two halves.
• A max heap holds the smaller half and a min heap holds the larger half, with their sizes differing by at most one.
• Lazy deletion marks a value as removed with a count, and drops it only when it reaches a heap top.
• Pruning both heap tops after every change keeps the median correct, and the median function can then read the tops directly.
• Use a double for the average of an even window, or the fraction is lost.