The question

Given a stream of unsorted integers, find the median element in sorted order at any given time. So, we will be receiving a continuous stream of numbers in some random order and we don’t know the stream length in advance. Write a function that finds the median of the already received numbers efficiently at any time. We will be asked to find the median multiple times. Just to recall, median is the middle element in an odd length sorted array, and in the even case it’s the average of the middle elements.

The solution

The best solution consists on having two heaps, a max-heap and a min-heap. These heaps will follow two rules:

– The max-heap contains the smallest half of the elements, the min-heap contain the largest half

– The number of elements in the max-heap will always be the same as the min-heap or one more

There is a heap library for node, so I will use it for the implementation:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
var heap = require('heap');

var minHeap = [];
var maxHeap = [];
var total = 0;

function insert(num) {
  if (total % 2 === 0) {
    // If this is an even element add it to maxHeap
    heap.push(maxHeap, -1 * num);
    total++;

    if (minHeap.length === 0) {
      return;
    }

    // If maxHeap's root became greater than minHeap's root then swap the roots
    if (-1 * maxHeap[0] > minHeap[0]) {
      toMin = -1 * heap.pop(maxHeap);
      toMax = -1 * heap.pop(minHeap);
      heap.push(maxHeap, toMax);
      heap.push(minHeap, toMin);
    }
  } else {
    // If this is an even element add it to max head. Then pop the lowest element
    // and add it to the min heap
    var toMin = -1 * heap.pushpop(maxHeap, -1 * num);
    heap.push(minHeap, toMin);
    total++;
  }
}

function getMedian() {
  if (total % 2 === 0) {
    // If the number of elements is even then we need to get both roots and
    // divide them by two
    return (-1 * maxHeap[0] + minHeap[0]) / 2;
  } else {
    // If the number of elements is odd return the head of the max heap
    return -1 * maxHeap[0];
  }
}

function test() {
  insert(1);
  insert(2);
  insert(3);

  if (getMedian() === 2) {
    console.log('success');
  }

  insert(4);

  if (getMedian() === 2.5) {
    console.log('success');
  }

  insert(9);

  if (getMedian() === 3) {
    console.log('success');
  }

}

test(); // Prints success 3 times
[ application_design  computer_science  algorithms  javascript  programming  ]
Sorting algorithms computer_science algorithms javascript programming
Raft for reaching consensus computer_science algorithms
The Rabin-Karp algorithm computer_science algorithms javascript programming
Load testing a Rails app with Vegeta application_design programming
House painting problem computer_science algorithms javascript programming