Interview Cheat Sheets | Heaps Cheat Sheet

December 27th, 2023

Introduction

This article will serve to further summarize the excellent overview of hash maps from the tech interview handbook.

Overview

A heap is a specialized tree-based data structure that forms a complete tree satisfying the heap property.

• Max heap: The value of a node is the greatest among the node values in its entire subtree.
• Min heap: The value of a node is the smallest among the node values in its entire subtree.

For algorithm interviews, heaps and priority queues can be treated interchangeably. Heaps are useful for efficiently handling repeated removals of objects with the highest or lowest priority, especially when insertions are interspersed with removals of the root node.

Time Complexity

Techniques

Mention of k: If a problem involves finding the top or lowest k elements, it often signals the use of a heap. For example, in Top K Frequent Elements, employ a Min Heap of size k. Push elements into the heap, and when the size exceeds k, remove the minimum element to maintain the k largest elements.

MaxHeap Implementation

Below is an implementation of a MaxHeap class in TypeScript.

class MaxHeap {
  private heap: number[];

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

  private getParentIndex(index: number): number {
    return Math.floor((index - 1) / 2);
  }

  private getLeftChildIndex(index: number): number {
    return 2 * index + 1;
  }

  private getRightChildIndex(index: number): number {
    return 2 * index + 2;
  }

  private swap(i: number, j: number): void {
    [this.heap[i], this.heap[j]] = [this.heap[j], this.heap[i]];
  }

  private heapifyUp(index: number): void {
    while (index > 0) {
      const parentIndex = this.getParentIndex(index);
      if (this.heap[index] > this.heap[parentIndex]) {
        this.swap(index, parentIndex);
        index = parentIndex;
      } else {
        break;
      }
    }
  }

  private heapifyDown(index: number): void {
    const size = this.heap.length;

    while (true) {
      const leftChildIndex = this.getLeftChildIndex(index);
      const rightChildIndex = this.getRightChildIndex(index);

      let largestIndex = index;

      if (
        leftChildIndex < size &&
        this.heap[leftChildIndex] > this.heap[largestIndex]
      ) {
        largestIndex = leftChildIndex;
      }

      if (
        rightChildIndex < size &&
        this.heap[rightChildIndex] > this.heap[largestIndex]
      ) {
        largestIndex = rightChildIndex;
      }

      if (index !== largestIndex) {
        this.swap(index, largestIndex);
        index = largestIndex;
      } else {
        break;
      }
    }
  }

  insert(value: number): void {
    this.heap.push(value);
    this.heapifyUp(this.heap.length - 1);
  }

  extractMax(): number | undefined {
    if (this.heap.length === 0) {
      return undefined;
    }

    const max = this.heap[0];
    const lastElement = this.heap.pop();

    if (this.heap.length > 0 && lastElement !== undefined) {
      this.heap[0] = lastElement;
      this.heapifyDown(0);
    }

    return max;
  }
}

Min Heap Implementation

Below is an implementation of a MinHeap class in TypeScript.

class MinHeap<T> {
  private heap: T[] = [];

  private swap(index1: number, index2: number): void {
    [this.heap[index1], this.heap[index2]] = [
      this.heap[index2],
      this.heap[index1],
    ];
  }

  private getParentIndex(index: number): number {
    return Math.floor((index - 1) / 2);
  }

  private getLeftChildIndex(index: number): number {
    return 2 * index + 1;
  }

  private getRightChildIndex(index: number): number {
    return 2 * index + 2;
  }

  private heapifyUp(): void {
    let currentIndex = this.heap.length - 1;

    while (currentIndex > 0) {
      const parentIndex = this.getParentIndex(currentIndex);

      // Assume T has properties named 'distance' and 'idx'
      if (
        this.heap[parentIndex]["distance"] > this.heap[currentIndex]["distance"]
      ) {
        this.swap(parentIndex, currentIndex);
        currentIndex = parentIndex;
      } else {
        break;
      }
    }
  }

  private heapifyDown(idx?: number): void {
    let currentIndex = idx ? idx : 0;

    while (true) {
      const leftChildIndex = this.getLeftChildIndex(currentIndex);
      const rightChildIndex = this.getRightChildIndex(currentIndex);
      let smallestChildIndex = null;

      // Assume T has properties named 'distance' and 'idx'
      if (
        leftChildIndex < this.heap.length &&
        this.heap[leftChildIndex]["distance"] <
          this.heap[currentIndex]["distance"]
      ) {
        smallestChildIndex = leftChildIndex;
      }

      if (
        rightChildIndex < this.heap.length &&
        this.heap[rightChildIndex]["distance"] <
          this.heap[currentIndex]["distance"]
      ) {
        smallestChildIndex =
          this.heap[rightChildIndex]["distance"] <
          this.heap[leftChildIndex]["distance"]
            ? rightChildIndex
            : smallestChildIndex;
      }

      if (smallestChildIndex === null) {
        break;
      }

      this.swap(currentIndex, smallestChildIndex);
      currentIndex = smallestChildIndex;
    }
  }

  buildHeap(values: T[]): void {
    this.heap = values;
    const n = this.heap.length;

    // Start from the last non-leaf node and move up
    for (let i = Math.floor(n / 2) - 1; i >= 0; i--) {
      this.heapifyDown(i);
    }
  }

  insert(value: T): void {
    this.heap.push(value);
    this.heapifyUp();
  }

  extractMin(): T | undefined {
    if (this.heap.length === 0) {
      return undefined;
    }

    if (this.heap.length === 1) {
      return this.heap.pop()!;
    }

    const min = this.heap[0];
    this.heap[0] = this.heap.pop()!;
    this.heapifyDown();

    return min;
  }

  peekMin(): T | undefined {
    return this.heap.length > 0 ? this.heap[0] : undefined;
  }

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

  isEmpty(): boolean {
    return this.heap.length === 0;
  }
}

// Example usage:
const minHeap = new MinHeap<number>();
minHeap.insert(4);
minHeap.insert(2);
minHeap.insert(7);
minHeap.insert(1);

console.log(minHeap.extractMin()); // Output: 1
console.log(minHeap.peekMin()); // Output: 2
console.log(minHeap.size()); // Output: 3
console.log(minHeap.isEmpty()); // Output: false

Essential Questions

• Merge K-Sorted Lists
• K Closest Points to Origin - My solution

Recommended Practice Questions

• Top K Frequent Elements
• Find Median from Data Stream