Sorting has become one of the fundamental techniques to perform operations whether it's a database system or an app that wants to store numbers or names alphabetically. Many sorting algorithms came into development over the years, and Heap Sort is one of them. In the following article, we will explore the heap sort – How the algorithm works, its complexities, and how to implement it in JavaScript.
What is sorting?
Sorting is a technique used for ordering the elements of a list in a specific order. The order can be numerical or alphabetic. Sorting technique has various applications such as database sorting, sorting customer entries, sorting data in data visualization, or arranging form data in web apps.
What is a heap?
A heap is a complete binary tree, which means each node in the tree is filled and has the utmost two children nodes.
What is heap sort?
Heap sort is a sorting technique in which the entire array gets divided into two parts- the sorted region and the unsorted region. It eliminates the elements one at a time from the unsorted part and puts them in the sorted area of the array.
Working of the Heap sort algorithm:
Here is how the heap sort algorithm works.
- The first step of the algorithm is to make a heap by altering the elements in the array.
- In the second phase, the root element of the unsorted area gets deleted. The deleted element gets placed at the end of the array. Thus, the element gets placed in the sorted area.
Heap sort implementation in JavaScript:
Code:
<!DOCTYPE html>
<html>
<body>
<script>
function Sort(arr)
{
var n = arr.length;
// Building heap
for (var i = Math.floor(n / 2) - 1; i >= 0; i--)
heapify(arr, n, i);
// One by one extract an element from heap
for (var i = n - 1; i > 0; i--) {
var temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
heapify(arr, i, 0);
}
}
function heapify(arr, n, i)
{
var largest = i; // Initializing largest element as the root
var l = 2 * i + 1;
var r = 2 * i + 2;
if (l < n && arr[l] > arr[largest])
largest = l;
if (r < n && arr[r] > arr[largest])
largest = r;
if (largest != i) {
var swap = arr[i];
arr[i] = arr[largest];
arr[largest] = swap;
heapify(arr, n, largest);
}
}
/* function to print the array */
function printArray(arr)
{
var n = arr.length;
for (var i = 0; i < n; ++i)
document.write(arr[i] + " ");
}
var arr = [ 81, 89, 9, 11, 14, 76, 54, 22 ];
var n = arr.length;
document.write( "The array is <br>");
printArray(arr)
Sort(arr);
document.write( "<br> Sorted array is <br>");
printArray(arr);
</script>
</body>
</html>
Output:
Working of the above heap sort program
An array arr[] has the following elements:
81,89,9,11,14,76,54,22
The array elements after converting into a max heap:
89,81,76,22,14,9,54,11
Here, the root element = 89, and the last element = 11
Delete the root element by swapping 89 with the last element, 11. After deleting the element and converting it into the max heap, the new array elements are:
81,22,76,11,14,9,54,89
Now, the root element = 81 and the last element = 54
Delete the root element by swapping 81 with the last element, 54. After deleting the element and converting it into the max
heap, the new array elements are:
76, 22,54,11,14,9,81,89
Now, the root element = 76 and the last element = 9
Delete the root element by swapping 76 with the last element 9. After deleting the element and converting it into the max
heap, the new array elements are:
54,22,9,11,14,76,81,89
Now, the root element=54 and the last element=14
Delete the root element by swapping 54 with the last element, 14. After deleting the element and converting it into the max
heap, the new array elements are:
22,14,9,11,54,76,81,89
Now, the root element = 22, and the last element = 11
Delete the root element by swapping 22 with the last element 11. After deleting the element and converting it into the max
heap, the new array elements are:
14,11,9,22,54,76,81,89
Now, the root element=14, and the last element=9
Delete the root element by swapping 14 with the last element 9. After deleting the element and converting it into the max
heap, the new array elements are:
11,9,14,22,54,76,81,89
Now, the root element = 11, and the last element = 9
Delete the root element by swapping 11 with the last element, 9. After deleting the element and converting it into the max
heap, the new array elements are:
9,11,14,22,54,76,81,89
Now, the last element of the heap is 9. After deleting it, the heap will be empty. After completing the sorting, the array elements are:
9,11,14,22,54,76,81,89
Time and space complexities of Heap Sort
Heap Sort’s best-case complexity is O(n*logn) which happens when the array is already sorted.
Its average-case complexity is O(n*logn) which happens when the array elements are jumbled.
Its worst-case complexity is O(n*logn) which happens when the array elements must get sorted in reverse order. Thus, it is relatively slow compared to quick sort.
It has a space complexity of O(n).
To sum up:
In the heap sort, the entire array gets divided into two parts- the sorted region and the unsorted region. Heap sort is one of the most widely used sorting techniques. It eliminates one element at a time from the unsorted part and places it in the sorted area of the array. Though heap sort is not the fastest possible algorithm, it is particularly advantageous when there is a need for a robust and stable sorting algorithm.