Implementing a Binary Heap in JavaScript

Binary heaps are fundamental data structures used in various algorithms, including priority queues and heapsort. This challenge asks you to implement a binary heap in JavaScript, focusing on the core operations of insertion, extraction of the minimum element (for a min-heap), and heapifying an array. A well-implemented binary heap provides efficient logarithmic time complexity for these operations.

Problem Description

You are tasked with creating a BinaryHeap class in JavaScript. This class should support the following operations:

• constructor(): Initializes an empty binary heap.
• insert(value): Inserts a new value into the heap, maintaining the heap property.
• extractMin(): Removes and returns the minimum value (root) from the heap, re-heapifying the remaining elements to maintain the heap property. Returns undefined if the heap is empty.
• heapify(arr): Transforms an arbitrary array into a binary heap in-place. This should be done efficiently, typically using a bottom-up approach.
• size(): Returns the number of elements in the heap.
• isEmpty(): Returns true if the heap is empty, false otherwise.

The heap should be a min-heap, meaning the smallest element is always at the root.

Key Requirements:

• The implementation should be efficient, aiming for logarithmic time complexity for insertion and extraction.
• The heap property (parent node is always smaller than or equal to its children) must be maintained after each operation.
• The heapify function should efficiently convert an unsorted array into a valid min-heap.

Expected Behavior:

• insert() should correctly place the new element in the heap and bubble it up to its correct position.
• extractMin() should return the smallest element and re-heapify the remaining elements.
• heapify() should transform the input array into a valid min-heap.
• size() should accurately reflect the number of elements in the heap.
• isEmpty() should correctly indicate whether the heap is empty.

Edge Cases to Consider:

• Empty heap scenarios for extractMin() and size().
• Duplicate values in the heap.
• Large input arrays for heapify().
• Inserting very large or very small values.

Examples

Example 1:

Input:
heap = new BinaryHeap();
heap.insert(5);
heap.insert(2);
heap.insert(8);
heap.insert(1);

Output: 1
Explanation: extractMin() removes and returns the minimum value (1) from the heap. The heap is then re-heapified.

Example 2:

Input: arr = [4, 1, 3, 2, 16, 9, 10, 14, 8, 7];
heap = new BinaryHeap();
heap.heapify(arr);

Output: arr = [1, 2, 3, 4, 7, 9, 10, 14, 8, 16]
Explanation: The heapify function transforms the input array into a min-heap in-place.

Example 3: (Edge Case)

Input: heap = new BinaryHeap();
Output: undefined
Explanation: extractMin() on an empty heap returns undefined.

Constraints

• The heap will store numbers.
• The heapify function will receive an array of numbers.
• The size of the array passed to heapify can be up to 10,000 elements.
• The time complexity of insert and extractMin should be O(log n), where n is the number of elements in the heap.
• The time complexity of heapify should be O(n).

Notes

• Consider using an array to represent the heap.
• The index of a node's children can be calculated as 2i + 1 (left) and 2i + 2 (right), where i is the index of the parent node.
• The index of a node's parent can be calculated as Math.floor((i - 1) / 2).
• The heapify operation can be implemented using a bottom-up approach, starting from the last non-leaf node.
• Focus on clarity and efficiency in your implementation. Good variable names and comments will be helpful.