heap Sort Algorithm
Heap sort algorithm is a comparison-based sorting technique that utilizes a special data structure known as a binary heap. It is an in-place sorting algorithm, meaning that it doesn't require any additional memory to be allocated for temporary storage. Heap sort works by first building a binary heap (either a max-heap or a min-heap) from the input data, and then repeatedly extracting the maximum or minimum element from the heap and inserting it into a sorted array. This process continues until the heap becomes empty and the sorted array contains all the elements from the original input data.
A binary heap is essentially a complete binary tree with the property that each parent node is either greater than or equal to (in case of a max-heap) or less than or equal to (in case of a min-heap) its child nodes. Heap sort takes advantage of this property by ensuring that the largest or smallest element is always at the root of the heap, making it easy to extract and place in the sorted array. After extracting the root element, the algorithm restores the heap property by moving elements within the heap, a process called "heapifying". This "heapify" operation is repeated until the entire input data has been sorted. The time complexity of heap sort is O(n log n) in the worst, average, and best cases, making it an efficient and reliable sorting algorithm for various applications.
let arrayLength = 0
/* to create MAX array */
function heapRoot (input, i) {
const left = 2 * i + 1
const right = 2 * i + 2
let max = i
if (left < arrayLength && input[left] > input[max]) {
max = left
}
if (right < arrayLength && input[right] > input[max]) {
max = right
}
if (max !== i) {
swap(input, i, max)
heapRoot(input, max)
}
}
function swap (input, indexA, indexB) {
[input[indexA], input[indexB]] = [input[indexB], input[indexA]]
}
function heapSort (input) {
arrayLength = input.length
for (let i = Math.floor(arrayLength / 2); i >= 0; i -= 1) {
heapRoot(input, i)
}
for (let i = input.length - 1; i > 0; i--) {
swap(input, 0, i)
arrayLength--
heapRoot(input, 0)
}
}
const arr = [3, 0, 2, 5, -1, 4, 1]
heapSort(arr)
console.log(arr)
