Implementing a Max Heap in JavaScript

A max heap is a specialized tree-based data structure that satisfies the max-heap property: for every node i other than the root, the value of node i is less than or equal to the value of its parent. This challenge asks you to implement a Max Heap data structure in JavaScript, enabling efficient retrieval of the maximum element and supporting insertion and deletion operations while maintaining the heap property. Max heaps are useful in priority queues and heapsort algorithms.

Problem Description

You are tasked with creating a MaxHeap class in JavaScript. This class should provide the following functionalities:

• constructor(): Initializes an empty max heap.
• insert(value): Inserts a new value into the heap, maintaining the max-heap property.
• extractMax(): Removes and returns the maximum value (root) from the heap, maintaining the max-heap property. If the heap is empty, it should return undefined.
• peek(): Returns the maximum value (root) from the heap without removing it. If the heap is empty, it should return undefined.
• size(): Returns the number of elements in the heap.
• isEmpty(): Returns true if the heap is empty, false otherwise.

The heap should be implemented using an array to represent the tree structure. The index 0 of the array will represent the root of the heap. The children of a node at index i are located at indices 2*i + 1 and 2*i + 2.

Key Requirements:

• The insert and extractMax methods must maintain the max-heap property after each operation.
• The implementation should be efficient, minimizing unnecessary operations.
• The code should be well-documented and easy to understand.

Expected Behavior:

The insert method should add the new element to the end of the array and then "heapify up" by comparing it with its parent and swapping if necessary until the max-heap property is satisfied. The extractMax method should remove the root element, replace it with the last element in the array, reduce the array size by one, and then "heapify down" by comparing the new root with its children and swapping with the larger child until the max-heap property is satisfied.

Examples

Example 1:

Input:
heap = new MaxHeap();
heap.insert(5);
heap.insert(10);
heap.insert(3);
heap.extractMax();

Output:
10

Explanation: The heap initially contains [10, 5, 3]. extractMax() removes 10, replaces it with 3, and heapifies down, resulting in [5, 3].

Example 2:

Input:
heap = new MaxHeap();
heap.insert(4);
heap.insert(1);
heap.insert(3);
heap.insert(2);
heap.insert(16);
heap.insert(9);
heap.insert(10);
heap.insert(14);
heap.insert(8);
heap.insert(7);
heap.extractMax();
heap.extractMax();

Output:
16
14

Explanation: The heap is built and then the two largest elements are extracted.

Example 3: (Edge Case - Empty Heap)

Input:
heap = new MaxHeap();
heap.extractMax();
heap.peek();

Output:
undefined
undefined

Explanation: Demonstrates behavior when the heap is empty.

Constraints

• The input values for insertion can be any number (integers or floats).
• The heap size will not exceed 10,000 elements.
• The time complexity of insert and extractMax should be O(log n), where n is the number of elements in the heap.
• The array representing the heap should not be exposed externally.

Notes

• Consider using helper functions like heapifyUp and heapifyDown to encapsulate the logic for maintaining the heap property.
• Pay close attention to the indices when accessing parent and child nodes in the array representation of the heap.
• Remember to handle the edge case of an empty heap gracefully.
• Think about how to efficiently swap elements within the array.