Delving into the Min Heap

Definition and Structure

In a min heap, the smallest element is always at the root. This ordering means that if you traverse the heap level by level, each parent is less than or equal to its children. This characteristic is key for applications where you need rapid access to the minimum element.

Core Operations

• Insertion: When a new element is added, it is placed at the next available position (maintaining the complete tree property) and then “bubbled up” to restore the min heap property.
• Extraction (or Removal) of Minimum: Removing the root element requires replacing it with the last element in the heap, followed by a “bubble down” process to maintain the heap property.
• Heapify: This is the process of creating a heap from an unordered array. It rearranges the elements to satisfy the heap condition, typically in O(n) time.

Time Complexity

• Insertion: O(log n)
• Extraction: O(log n)
• Heap Construction (Heapify): O(n)

class MinHeap {
  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(index1: number, index2: number): void {
    [this.heap[index1], this.heap[index2]] = [
      this.heap[index2],
      this.heap[index1],
    ];
  }

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

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

  removeMin(): number | null {
    if (this.heap.length === 0) return null;
    if (this.heap.length === 1) return this.heap.pop() || null;

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

  private heapifyDown(): void {
    let index = 0;
    const length = this.heap.length;

    while (this.getLeftChildIndex(index) < length) {
      let smallerChildIndex = this.getLeftChildIndex(index);
      const rigthChildeIndex = this.getRightChildIndex(index);

      if (
        rigthChildeIndex < length &&
        this.heap[rigthChildeIndex] < this.heap[smallerChildIndex]
      ) {
        smallerChildIndex = rigthChildeIndex;
      }

      if (this.heap[index] <= this.heap[smallerChildIndex]) {
        break;
      }

      this.swap(index, smallerChildIndex);
      index = smallerChildIndex;
    }
  }

  peek(): number | null {
    if (this.heap.length === 0) return null;
    return this.heap[0];
  }

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

const minHeap = new MinHeap();

minHeap.insert(5);
minHeap.insert(3);
minHeap.insert(8);
minHeap.insert(1);
minHeap.insert(6);

console.log("Heap after insertions: ", minHeap); // Check the structure

// Peek at the minimum element
console.log("Peek minimum: ", minHeap.peek()); // Output should be 1, the smallest element

// Remove the minimum element
console.log("Remove minimum: ", minHeap.removeMin()); // Output should be 1
console.log("Heap after removing minimum: ", minHeap);

// Insert additional elements
minHeap.insert(2);
minHeap.insert(4);
console.log("Heap after additional insertions: ", minHeap);

// Continue removing the minimum element until the heap is empty
while (!minHeap.isEmpty()) {
  console.log("Remove minimum: ", minHeap.removeMin());
  console.log("Current heap: ", minHeap);
}