Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

Practice › Heap & Priority Queue

Median of a Running Stream

Hard · Heap & Priority Queue · Asked at Amazon, Google, Microsoft, Meta, Apple

Numbers arrive one at a time. After each number, print the median of all numbers so far, with exactly one digit after the decimal point. For an even count, the median is the average of the two middle values.

Input

First line: n. Second line: n space-separated integers.

Output

n lines, the median after each insertion (e.g. 2.0, 2.5, -1.5).

Constraints

Two heaps: a max-heap with the smaller half and a min-heap with the larger half, balanced so their sizes differ by at most one. The median comes from their tops.

Example 1

Input

4
5 15 1 3

Output

5.0
10.0
5.0
4.0

Example 2

Input

3
-1 -2 -3

Output

-1.0
-1.5
-2.0

Hints

  1. Split the numbers into a lower half and an upper half.
  2. Store the lower half in a max-heap and the upper half in a min-heap, keeping their sizes equal or the lower half one larger. The median is the top of the lower heap, or the average of both tops.

Approach

For each new number: push it into the max-heap low, then move low's top into the min-heap high (so every element of low ≤ every element of high), and if high becomes bigger than low, move its top back. Now for an odd count the median is low.top; for an even count it is (low.top + high.top) / 2. The sum of two middles is an integer, so print sum/2 with one decimal: it ends in .0 or .5 exactly.

Complexity: O(n log n) time · O(n) space

Solution

C++ solution

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    priority_queue<long long> low;                                       // max-heap
    priority_queue<long long, vector<long long>, greater<long long>> high; // min-heap
    for (int i = 0; i < n; i++) {
        long long x;
        cin >> x;
        low.push(x);
        high.push(low.top());
        low.pop();
        if (high.size() > low.size()) {
            low.push(high.top());
            high.pop();
        }
        long long sum = low.size() > high.size() ? 2 * low.top() : low.top() + high.top();
        printf("%.1f\n", sum / 2.0);
    }
    return 0;
}

Python solution

import sys
import heapq

data = list(map(int, sys.stdin.read().split()))
low, high, out = [], [], []  # low is a max-heap (negated values)
for x in data[1:]:
    heapq.heappush(low, -x)
    heapq.heappush(high, -heapq.heappop(low))
    if len(high) > len(low):
        heapq.heappush(low, -heapq.heappop(high))
    s = -2 * low[0] if len(low) > len(high) else -low[0] + high[0]
    out.append(f"{s / 2:.1f}")
print("\n".join(out))

Java solution

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine().trim());
        StringTokenizer st = new StringTokenizer(br.readLine());
        PriorityQueue<Long> low = new PriorityQueue<>(Collections.reverseOrder()), high = new PriorityQueue<>();
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++) {
            long x = Long.parseLong(st.nextToken());
            low.add(x);
            high.add(low.poll());
            if (high.size() > low.size()) low.add(high.poll());
            long sum = low.size() > high.size() ? 2 * low.peek() : low.peek() + high.peek();
            sb.append(String.format(Locale.ROOT, "%.1f", sum / 2.0));
            sb.append('\n');
        }
        System.out.print(sb);
    }
}

Solve Median of a Running Stream online · All practice problems