Implement a Binary Heap in JavaScript

Binary heaps are fundamental data structures used in various algorithms, including priority queues, heapsort, and graph algorithms like Dijkstra's. This challenge will guide you through implementing a binary heap, a key step towards mastering these advanced concepts.

Problem Description

Your task is to implement a Binary Heap data structure in JavaScript. A binary heap is a complete binary tree that satisfies the heap property. You should implement both a Min-Heap and a Max-Heap.

Key Requirements:

1. Heap Property:
   • Min-Heap: For any given node i, the value of node i is less than or equal to the values of its children. The smallest element is always at the root.
   • Max-Heap: For any given node i, the value of node i is greater than or equal to the values of its children. The largest element is always at the root.
2. Complete Binary Tree: All levels of the tree are fully filled except possibly the last level, which is filled from left to right. This property allows us to represent the heap efficiently using an array.
3. Core Operations: Implement the following methods:
   • insert(value): Adds a new element to the heap while maintaining the heap property.
   • extractRoot(): Removes and returns the root element (the minimum for Min-Heap, maximum for Max-Heap), then reorganizes the heap to maintain the heap property.
   • peek(): Returns the root element without removing it.
   • size(): Returns the number of elements in the heap.
   • isEmpty(): Returns true if the heap is empty, false otherwise.

Expected Behavior:

• The heap should correctly maintain its property after insertions and extractions.
• The extractRoot() operation should always return the correct extreme element (min or max).
• The heap should be able to handle duplicate values.

Edge Cases to Consider:

• Inserting into an empty heap.
• Extracting from an empty heap (should return null or undefined).
• Extracting the last element.
• Heaps with only one element.

Examples

Example 1: Min-Heap insert and peek

Input:
const minHeap = new MinHeap();
minHeap.insert(3);
minHeap.insert(1);
minHeap.insert(4);
minHeap.insert(1); // Duplicate
minHeap.insert(5);
minHeap.insert(9);
minHeap.insert(2);

Output:
minHeap.peek() // Should return 1
minHeap.size() // Should return 7

Explanation: After inserting the elements, the Min-Heap arranges them such that the smallest element is at the root. The order in the internal array representation will vary depending on the insertion order, but the root will always be the minimum value.

Example 2: Min-Heap extractRoot

Input:
// Continuing from Example 1
const minHeap = new MinHeap();
minHeap.insert(3);
minHeap.insert(1);
minHeap.insert(4);
minHeap.insert(1);
minHeap.insert(5);
minHeap.insert(9);
minHeap.insert(2);

const firstExtract = minHeap.extractRoot(); // Should return 1
const secondExtract = minHeap.extractRoot(); // Should return 1
const thirdExtract = minHeap.extractRoot(); // Should return 2

Output:
firstExtract // 1
secondExtract // 1
thirdExtract // 2
minHeap.peek() // Should return 3
minHeap.size() // Should return 4

Explanation: Each extractRoot() call removes the smallest element and re-heapifies. The duplicate '1's are removed first, followed by '2'.

Example 3: Max-Heap insert and extractRoot

Input:
const maxHeap = new MaxHeap();
maxHeap.insert(10);
maxHeap.insert(5);
maxHeap.insert(15);
maxHeap.insert(20);
maxHeap.insert(8);

const extractedMax1 = maxHeap.extractRoot(); // Should return 20
const extractedMax2 = maxHeap.extractRoot(); // Should return 15

Output:
extractedMax1 // 20
extractedMax2 // 15
maxHeap.peek() // Should return 10
maxHeap.size() // Should return 3

Explanation: The Max-Heap ensures the largest element is always at the root. extractRoot() removes the largest and re-organizes.

Example 4: Edge Case - Empty Heap

Input:
const minHeap = new MinHeap();

minHeap.extractRoot(); // Should return undefined or null
minHeap.peek(); // Should return undefined or null
minHeap.isEmpty(); // Should return true

Explanation: Operations on an empty heap should be handled gracefully.

Constraints

• The heap will store numbers.
• The values of numbers will be within the standard JavaScript number range.
• The number of elements in the heap will not exceed 1,000,000.
• The time complexity for insert and extractRoot operations should ideally 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

• You can represent the binary heap using an array. The children of an element at index i are typically at indices 2*i + 1 (left child) and 2*i + 2 (right child). The parent of an element at index i is at index Math.floor((i - 1) / 2).
• When implementing insert, you'll need to "bubble up" the new element to its correct position.
• When implementing extractRoot, you'll typically replace the root with the last element, remove the last element, and then "bubble down" the new root to its correct position.
• Consider creating helper methods for swap, bubbleUp, and bubbleDown to keep your code clean.
• You will need to implement two separate classes, MinHeap and MaxHeap.