Implement Heapsort in JavaScript

This challenge asks you to implement the heapsort algorithm in JavaScript. Heapsort is an efficient, comparison-based sorting algorithm known for its O(n log n) time complexity in the average and worst cases. Understanding heapsort is crucial for grasping advanced data structures and algorithms.

Problem Description

Your task is to write a JavaScript function that takes an array of numbers and sorts it in ascending order using the heapsort algorithm.

Key Requirements:

• The function should modify the input array in-place.
• The sorting must be done using the heapsort algorithm, which involves two main phases:
  1. Heapify: Build a max-heap from the input array.
  2. Sort: Repeatedly extract the maximum element from the heap (which is always the root) and place it at the end of the sorted portion of the array.
• You will need helper functions for heap operations like heapify (to build the heap) and siftDown (to maintain the heap property after element extraction).

Expected Behavior:

The function should return the sorted array. The original array passed as an argument should be modified directly.

Edge Cases to Consider:

• An empty array.
• An array with a single element.
• An array with duplicate elements.
• An array that is already sorted (ascending or descending).

Examples

Example 1:

Input: [4, 10, 3, 5, 1]
Output: [1, 3, 4, 5, 10]
Explanation: The input array is transformed into a max-heap, and then elements are extracted and placed in their sorted positions.

Example 2:

Input: [12, 11, 13, 5, 6, 7]
Output: [5, 6, 7, 11, 12, 13]
Explanation: Demonstrates sorting a moderately sized array with various values.

Example 3:

Input: []
Output: []
Explanation: An empty array should remain empty.

Example 4:

Input: [5]
Output: [5]
Explanation: An array with a single element is already sorted.

Constraints

• The input will be an array of numbers.
• The array can contain positive, negative, or zero values.
• The size of the array (n) will be between 0 and 10,000.
• The time complexity of your solution should be O(n log n).
• The space complexity should be O(1) (in-place sorting).

Notes

• Remember that in a 0-indexed array, 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).
• When building the max-heap, you should start from the last non-leaf node and work your way up to the root. The last non-leaf node is at index Math.floor(n / 2) - 1.
• The siftDown (or heapifyDown) operation is crucial for maintaining the heap property after swapping elements.
• Consider implementing a helper function to swap elements within the array.