Implement a Max Heap Data Structure in JavaScript

This challenge requires you to implement a Max Heap data structure in JavaScript. A Max Heap is a specialized tree-based data structure that satisfies the heap property: in a Max Heap, for any given node C, if P is a parent node of C, then the value of P is greater than or equal to the value of C. Max Heaps are fundamental for various algorithms, including priority queues and heap sort, making their implementation a valuable exercise in understanding tree structures and their operations.

Problem Description

Your task is to create a JavaScript class named MaxHeap that encapsulates the functionality of a Max Heap. The heap will be implemented using an array. You need to implement the following core methods:

• constructor(array): Initializes the heap. If an array is provided, it should build a Max Heap from that array. Otherwise, it should create an empty heap.
• insert(value): Adds a new value to the heap, maintaining the Max Heap property.
• extractMax(): Removes and returns the maximum element from the heap (the root), also maintaining the Max Heap property.
• peek(): Returns the maximum element from the heap without removing it.
• size(): Returns the number of elements currently in the heap.
• isEmpty(): Returns true if the heap is empty, false otherwise.

Key Requirements:

1. Array-based Implementation: Use a JavaScript array to store the heap elements.
2. Max Heap Property: Ensure that for every node i, heap[i] >= heap[2*i + 1] and heap[i] >= heap[2*i + 2] (if children exist).
3. Efficient Operations: insert and extractMax should aim for O(log n) time complexity, where n is the number of elements in the heap. peek, size, and isEmpty should be O(1).
4. Heapify on Construction: If an initial array is provided, the constructor should efficiently build the Max Heap in O(n) time.

Expected Behavior:

• insert should place the new value at the end of the array and then "bubble up" (or "heapify up") to its correct position.
• extractMax should replace the root with the last element, remove the last element, and then "bubble down" (or "heapify down") the new root to its correct position.
• peek should simply return the element at index 0.

Edge Cases to Consider:

• Empty heap: Operations on an empty heap.
• Heap with a single element.
• Inserting duplicate values.
• Extracting from a heap that becomes empty.

Examples

Example 1:

const heap = new MaxHeap([3, 1, 4, 1, 5, 9, 2, 6]);
console.log(heap.peek()); // Expected: 9
console.log(heap.extractMax()); // Expected: 9
console.log(heap.extractMax()); // Expected: 6
console.log(heap.size()); // Expected: 6

Explanation: The initial array is transformed into a Max Heap. The maximum element (9) is at the root. Extracting 9, then 6, maintains the heap property.

Example 2:

const heap = new MaxHeap();
heap.insert(10);
heap.insert(5);
heap.insert(15);
heap.insert(20);
heap.insert(3);

console.log(heap.peek()); // Expected: 20
console.log(heap.extractMax()); // Expected: 20
console.log(heap.extractMax()); // Expected: 15
console.log(heap.extractMax()); // Expected: 10
console.log(heap.extractMax()); // Expected: 5
console.log(heap.extractMax()); // Expected: 3
console.log(heap.isEmpty()); // Expected: true

Explanation: Elements are inserted one by one, and the heap property is maintained. Extracting elements yields them in descending order.

Example 3: Heapify Construction

const initialArray = [12, 11, 13, 5, 6, 7];
const heap = new MaxHeap(initialArray);

// The internal array representation of the heap after construction might look something like:
// [13, 12, 7, 5, 6, 11] (order may vary slightly depending on specific heapify implementation)

console.log(heap.peek()); // Expected: 13
console.log(heap.extractMax()); // Expected: 13
console.log(heap.peek()); // Expected: 12

Explanation: The constructor efficiently builds a Max Heap from the provided unsorted array. The root will always be the maximum value.

Constraints

• The values in the heap will be numbers.
• The input array to the constructor, if provided, will contain only numbers.
• The number of elements in the heap will not exceed 10,000.
• Implementations should aim for optimal time complexity as described in the problem description.

Notes

• Remember that array indices in JavaScript are 0-based. This means for a node at index i:
  • Its left child is at 2*i + 1.
  • Its right child is at 2*i + 2.
  • Its parent is at Math.floor((i - 1) / 2).
• The heapifyUp (or bubbleUp) and heapifyDown (or bubbleDown) helper methods will be crucial for maintaining the heap property after insertions and extractions.
• For efficient heap construction from an array, consider starting the heapifyDown process from the last non-leaf node and working upwards towards the root. The index of the last non-leaf node is Math.floor(n/2) - 1, where n is the number of elements.