Implement a Min Heap Data Structure in JavaScript

This challenge asks you to build a Min Heap data structure from scratch in JavaScript. A Min Heap is a binary tree-based data structure where the value of each parent node is less than or equal to the value of its child nodes. This property makes Min Heaps extremely efficient for tasks like priority queues, sorting (Heap Sort), and finding the k-th smallest element.

Problem Description

Your task is to create a MinHeap class in JavaScript that supports the following operations:

• insert(value): Adds a new value to the heap while maintaining the min-heap property.
• extractMin(): Removes and returns the smallest element from the heap, maintaining the min-heap property. If the heap is empty, it should return null or undefined.
• peek(): Returns the smallest element in the heap without removing it. If the heap is empty, it should return null or undefined.
• size(): Returns the number of elements currently in the heap.
• isEmpty(): Returns true if the heap is empty, false otherwise.

The internal representation of the heap can be an array. You'll need to implement the logic for heapify-up (percolate up) and heapify-down (percolate down) operations to ensure the min-heap property is preserved after insertions and deletions.

Key Requirements:

• The MinHeap class should be instantiated without any initial elements.
• The heap should store numerical values.
• The insert operation should correctly place the new element and bubble it up to its appropriate position.
• The extractMin operation should remove the root (smallest element), replace it with the last element, and then bubble that element down to its correct position.
• The peek operation should simply return the root element.

Edge Cases:

• Inserting into an empty heap.
• Extracting the last element from the heap.
• Extracting from an empty heap.
• Heap with only one element.

Examples

Example 1:

Input:
const heap = new MinHeap();
heap.insert(10);
heap.insert(5);
heap.insert(15);
heap.insert(2);

Output:
heap.peek() // 2
heap.extractMin() // 2
heap.peek() // 5
heap.extractMin() // 5
heap.size() // 2
heap.insert(8);
heap.peek() // 8

Explanation:

1. insert(10): Heap: [10]
2. insert(5): Heap: [5, 10] (5 bubbles up)
3. insert(15): Heap: [5, 10, 15]
4. insert(2): Heap: [2, 5, 15, 10] (2 bubbles up to the root)
5. peek() returns 2.
6. extractMin() removes 2. The heap becomes [10, 5, 15]. Then 10 is moved to the root and bubbles down to [5, 10, 15].
7. peek() returns 5.
8. extractMin() removes 5. The heap becomes [15, 10]. Then 15 is moved to the root and bubbles down to [10, 15].
9. size() returns 2.
10. insert(8): Heap: [8, 10, 15] (8 bubbles up)
11. peek() returns 8.

Example 2:

Input:
const heap = new MinHeap();
heap.insert(3);
heap.insert(1);
heap.insert(4);
heap.insert(1);
heap.insert(5);
heap.insert(9);
heap.insert(2);
heap.insert(6);

Output:
heap.extractMin() // 1
heap.extractMin() // 1
heap.extractMin() // 2
heap.extractMin() // 3
heap.size() // 4

Explanation: The heap is built with the given numbers. The first two extractMin calls return the two instances of 1. Subsequent calls return 2, then 3. The size is 4.

Example 3: (Edge Case)

Input:
const heap = new MinHeap();
heap.insert(100);

Output:
heap.extractMin() // 100
heap.extractMin() // null
heap.peek() // null
heap.size() // 0
heap.isEmpty() // true

Explanation: Extracting the only element leaves the heap empty. Subsequent extractMin and peek operations on an empty heap return null. isEmpty() returns true.

Constraints

• The heap will store non-negative integer values.
• The number of elements in the heap will not exceed 1,000,000.
• The time complexity for insert and extractMin operations should be O(log n), where n is the number of elements in the heap.
• The time complexity for peek, size, and isEmpty operations should be O(1).

Notes

• Remember that in an array-based heap representation, for a node at index i:
  • 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).
• When implementing extractMin, be careful with the order of operations: swap the root with the last element, remove the last element, and then perform the heapify-down operation.
• Consider how you will handle duplicate values in the heap. The min-heap property should still be maintained.
• You can use a JavaScript array to store the heap elements.