What is Heap Sort Algorithm?

Article By Digamber Rawat Published on

One of the best sorting methods which are in place and there is no quadratic running time is known as Heap sort algorithm. There is significant involvement of the heap sort in the building of the heap sort data structure from the available array. If you are wondering how the array of numbers is converted into a heap data structure, then you will need to know more about heap.

Understanding Heap Sort Algorithm?

A unique tree-based structure of data is known as Heap, and it helps to satisfy the following –

DigitalOcean Affiliate

Shape Property: data structure of the heap is always a complete binary tree that means it has all levels of the tree fulfilled.

Heap Property: all the available nodes are either higher or smaller or equal to that of the children. If the guardian nodes are more significant, then the heap is termed as Max Heap, and if the nodes are smaller, then they are known as Min heap.

How Does Heap Sort Algorithm Works?

Heap sort algorithm is generally divided into two fundamental aspects which are:
Creating a Heap of the list/array which unsorted. Then, a newly sorted array is continuously created by removing the largest or the smallest of elements in an array. The heap gets rebuilt after each relocation..

After receiving an unsorted list, the very first step which is involved is the Heap Data Structure or also known as Max-Heap. As soon as this heap is built, the very first element is the smallest or can also be the largest.

We use the heap to utilize the rest of the elements that are used to decide on the very first element in a heap and then put into an array. You need to continually keep doing the same till the time there is a complete and refined sorted list.

Implementing Heap Sort Algorithm in JavaScript

A simple yet brilliant JavaScript program implementation has been mentioned related to the Heap sort algorithm.

var arrayLength;
/* Creating MAX array */
function heapMain(input, i) {
var left = 2 * i + 1;
var right = 2 * i + 2;
var 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);
heapMain(input, max);
}
}
function swap(input, i_A, i_B) {
var temp = input[i_A];
input[i_A] = input[i_B];
input[i_B] = temp;
}
function heapSort(input) {
arrayLength = input.length;
for (var i = Math.floor(arrayLength / 2); i >= 0; i -= 1) {
heapMain(input, i);
}
for (i = input.length - 1; i > 0; i--) {
swap(input, 0, i);
arrayLength--;
heapMain(input, 0);
}
}
var arr = [9, 2, 1, 2, -1, 4, 1];
heapSort(arr);
console.log(arr);

Complexity Analysis of Heap Sort

  • Worst Case Time Complexity: O(n*log n)
  • Best Case Time Complexity: O(n*log n)
  • Average Time Complexity: O(n*log n)
  • Space Complexity: O(1)

Heap sort is different from heap sort and it requires constant space so that it can create a sorting list.

Heap sort is quick and fast which is why it is used widely for sorting.

Digamber Rawat
Digamber Rawat

I am a software engineer from India, love to learn and write about latest web and mobile technologies like: MongoDB, Angular 2+, Firebase, Express JS, Python, Node JS, JavaScript, RxJS etc.