Efficient Usage of Heaps to Determine Prefix Medians in JavaScript

Introduction

Hello there, budding programmer! I hope you're ready because today we're going to dive deep into high-level data manipulation and increase our understanding of heaps . Heaps are fundamental data structures commonly used in algorithms. We're going to leverage their potential today in an interesting algorithmic problem. Are you ready for the challenge? Let's get started!

Task Statement

1

Heap and Its Operations

A heap is a specialized binary tree-based data structure that satisfies the heap property: for a Min Heap, every parent node is less than or equal to its child nodes; for a Max Heap, every parent node is greater than or equal to its child nodes. This property makes heaps particularly efficient for operations like finding the minimum or maximum value. In practice, heaps can be implemented using arrays. For a given node at index i in an array: Its left child is at index 2 * i + 1 Its right child is at index 2 * i + 2 Its parent is at index Math.floor((i - 1) / 2) In our context, we use two specific types of heaps: a Min Heap and a Max Heap . The Min Heap is used to store the larger half of the numbers seen so far, while the Max Heap stores the smaller half. JavaScript does not have built-in heap functionality, so we will implement one or use an external library. Here, we'll use simple custom implementations for MinHeap and MaxHeap .

Min Heap and Max Heap Implementation

Join the 1M+ learners on CodeSignal

Be a part of our community of 1M+ users who develop and demonstrate their skills on CodeSignal

JavaScript

class MinHeap {
  constructor() {
    this.heap = [];
  }

  add(value) {
    this.heap.push(value);
    this._heapifyUp();
  }

  poll() {
    if (this.size() === 0) return null;
    if (this.size() <= 1) return this.heap.pop();
    const root = this.heap[0];
    this.heap[0] = this.heap.pop();
    this._heapifyDown();
    return root;
  }

  peek() {
    return this.heap[0];
  }

  size() {
    return this.heap.length;
  }

  _heapifyUp() {
    let index = this.heap.length - 1;
    while (index > 0) {
      const parentIndex = Math.floor((index - 1) / 2);
      if (this.heap[parentIndex] <= this.heap[index]) break;
      [this.heap[parentIndex], this.heap[index]] = [this.heap[index], this.heap[parentIndex]];
      index = parentIndex;
    }
  }

  _heapifyDown() {
    let index = 0;
    while (2 * index + 1 < this.heap.length) {
      let leftChildIndex = 2 * index + 1;
      let rightChildIndex = 2 * index + 2;
      let swapIndex = leftChildIndex;
  
      if (rightChildIndex < this.heap.length) {
        if (this.heap[rightChildIndex] < this.heap[leftChildIndex]) {
          swapIndex = rightChildIndex;
        }
      }
  
      if (this.heap[index] <= this.heap[swapIndex]) break;
  
      [this.heap[index], this.heap[swapIndex]] = [this.heap[swapIndex], this.heap[index]];
      index = swapIndex;
    }
  }
}

class MaxHeap extends MinHeap {
  add(value) {
    super.add(-value);
  }

  poll() {
    return -super.poll();
  }

  peek() {
    return -super.peek();
  }
}

JavaScript

function prefixMedian(arr) {
  const minHeap = new MinHeap();
  const maxHeap = new MaxHeap();
  const medians = new Array(arr.length);
}

JavaScript

function prefixMedian(arr) {
  const minHeap = new MinHeap();
  const maxHeap = new MaxHeap();
  const medians = new Array(arr.length);

  for (const num of arr) {
    if (maxHeap.size() > 0 && num < maxHeap.peek()) {
      maxHeap.add(num);
    } else {
      minHeap.add(num);
    }
  }
}

JavaScript

function prefixMedian(arr) {
  const minHeap = new MinHeap();
  const maxHeap = new MaxHeap();
  const medians = new Array(arr.length);

  for (let i = 0; i < arr.length; i++) {
    const num = arr[i];
    if (maxHeap.size() > 0 && num < maxHeap.peek()) {
      maxHeap.add(num);
    } else {
      minHeap.add(num);
    }

    if (maxHeap.size() > minHeap.size()) {
      minHeap.add(maxHeap.poll());
    } else if (minHeap.size() > maxHeap.size() + 1) {
      maxHeap.add(minHeap.poll());
    }
  }
}

JavaScript

function prefixMedian(arr) {
  const minHeap = new MinHeap();
  const maxHeap = new MaxHeap();
  const medians = new Array(arr.length);

  for (let i = 0; i < arr.length; i++) {
    const num = arr[i];
    if (maxHeap.size() > 0 && num < maxHeap.peek()) {
      maxHeap.add(num);
    } else {
      minHeap.add(num);
    }

    if (maxHeap.size() > minHeap.size()) {
      minHeap.add(maxHeap.poll());
    } else if (minHeap.size() > maxHeap.size() + 1) {
      maxHeap.add(minHeap.poll());
    }

    if (minHeap.size() === maxHeap.size()) {
      medians[i] = maxHeap.peek();
    } else {
      medians[i] = minHeap.peek();
    }
  }

  return medians;
}

// Test the function
const arr = [1, 9, 2, 8, 3];
const medians = prefixMedian(arr);
console.log("Final Medians Array: ", medians); // Output: Final Medians Array:  [ 1, 1, 2, 2, 3 ]

Introduction

Task Statement

Heap and Its Operations

Min Heap and Max Heap Implementation

Join the 1M+ learners on CodeSignal

Initializing Heaps and Median Array

Distributing Elements into Heaps

Balancing Heaps

Extracting Prefix Medians

Lesson Summary