Calculating Median with a Min/Max Pair Heap

Javascript implementation of a Min/Max Pair Sort for calculating the median of a large time series of data.

by jordant

HTML

<link rel="stylesheet" href="https://s3.amazonaws.com/kiddsoftware-jsfiddle/mocha-1.9.0.css">
<script src="https://s3.amazonaws.com/kiddsoftware-jsfiddle/chai-jquery.js"></script>
<script src="https://s3.amazonaws.com/kiddsoftware-jsfiddle/mocha-1.9.0.js"></script>
<script src="https://s3.amazonaws.com/kiddsoftware-jsfiddle/chai-1.5.0.js"></script>
<!-- No need to change this -->http://jsfiddle.net/jordant/np87qctf/21/#set-as-base
<!-- Mocha test output goes here. -->
<div id="mocha"></div>

JavaScript

/*
 * Our application servers receive approximately 20 000
 * http requests  per second. Response timeout is 19000ms.
 * Implement a statistics collector that calculates the
 * median and average request response times for a 7 day
 * dataset.
 *
 * JT
 *
 * @see https://codeinhelsinki.wordpress.com/2017/09/29/median-of-a-time-series/ 
 */

'use strict';

// State collector
class StatsCollector {


    /**
     * Construct the object.
     * @param simulationMode Used for testing purposes because we don't have a massive dataset
     */
    constructor(simulationMode = false) {
        this.count = 0;
        this.total = 0;
        this.simulationMode = simulationMode;
        this.maxHeap = new PairHeap('max');
        this.minHeap = new PairHeap('min');
    }

    /**
     * Adds a value to the StatsCollector. Request timeouts are not considered here.
     */
    pushValue(responseTimeMs /*number*/ ) /*void*/ {
        this.total += responseTimeMs;
        this.count++;

        // sample approximately every second so we end up with around 1 stats per second.
        // for a 1 week period there is no need for 20,000 data points per second.
        // request timeouts are not handled here. 
        if (this.count % 20000 == 0 || this.simulationMode == true) {
            // ordinarily we would probably wrap this in a callback so that it won't block
            // the insertion of subsequent values. For this example just run it all syncronously.
            this.addToMinMaxHeap(responseTimeMs);
            this.balanceHeaps();

        }
    }

    getAverage() /*number*/ {
        return this.total / this.count;
    }

    getMedian() /*number*/ {
        console.log(this.minHeap.size, this.maxHeap.size)

        if (Math.abs(this.minHeap.size - this.maxHeap.size) === 1) {
            if (this.minHeap.size > this.maxHeap.size) {
                return this.minHeap.root.nodeValue;
            } else {
                return this.maxHeap.root.nodeValue;
          ...