Heapsort Implementation in JavaScript

Heapsort is an efficient, comparison-based sorting algorithm that leverages the properties of a binary heap data structure. It offers a guaranteed O(n log n) time complexity for both average and worst-case scenarios, making it a valuable tool for sorting large datasets. Your task is to implement the heapsort algorithm in JavaScript.

Problem Description

You are required to implement the heapsort algorithm in JavaScript. This involves two main phases:

1. Heapify: Convert the input array into a max-heap. A max-heap is a binary tree where the value of each node is greater than or equal to the value of its children.
2. Sort: Repeatedly extract the maximum element (root of the heap) and place it at the end of the sorted portion of the array. After each extraction, re-heapify the remaining elements to maintain the heap property.

Key Requirements:

• The function should take an array of numbers as input.
• The function should return a new sorted array (do not modify the original array).
• The implementation must adhere to the heapsort algorithm.
• The heapify process should be efficient (bottom-up approach is recommended).
• The sorting process should correctly place elements in ascending order.

Expected Behavior:

The function should correctly sort the input array in ascending order using the heapsort algorithm.

Edge Cases to Consider:

• Empty array: Should return an empty array.
• Array with one element: Should return the array as is.
• Array with duplicate elements: Should correctly sort the array with duplicates.
• Array with negative numbers: Should correctly sort the array with negative numbers.

Examples

Example 1:

Input: [5, 1, 4, 2, 8]
Output: [1, 2, 4, 5, 8]
Explanation: The input array is converted into a max-heap, then elements are repeatedly extracted and placed in the sorted portion of the array.

Example 2:

Input: [5, 1, 4, 2, 8, 0, 2]
Output: [0, 1, 2, 2, 4, 5, 8]
Explanation:  The algorithm correctly handles duplicate values and negative numbers.

Example 3:

Input: []
Output: []
Explanation: An empty array is returned as is.

Constraints

• The input array will contain only numbers (integers or floats).
• The array size can range from 0 to 10,000 elements.
• The algorithm should have a time complexity of O(n log n).
• The algorithm should have a space complexity of O(1) (in-place sorting, excluding the output array).

Notes

• Consider using a bottom-up approach for heapify, starting from the last non-leaf node.
• The heapify function is crucial for maintaining the heap property.
• Think about how to efficiently swap elements within the array.
• Remember that heapsort sorts in ascending order.
• While the algorithm is generally O(n log n), be mindful of potential inefficiencies in your implementation that could degrade performance.