Heap sort implementation using Javascript

Posted By : Rajan Rawat | 27-Nov-2017

Heap Sort

Heap sorting os technique which is based on comparison and binary heap data structure. This is very similar to the technique of selection sort in which we find the first highest element first and then place the element at the end. we repeat this same process for finding the remaining elements

What is the binary heap?

we define a complete binary tree first. A binary tree become complete binary tree when every level besides the last element is filled and all the nodes only as far as the left is possible

A complete binary tree is a binary tree in which items are stored in the special order means when the parent node is greater than the values of its two children nodes. This is process is called as max heap and other latter will you call min heap. This kind of heap can be represented as a binary tree or as an array

Representation for Binary Heap

So now we know that binary heap is a complete binary tree, so we can represent as an array and its an array based representation is very efficient. Just store the parent node at index I, for the left child calculation do 2*I and for the right child calculation and starts from the index 0

Heap Sort Algorithm

1. For the input data build the max heap

2. At this stage the largest item is on the root of the heap, Replace that item with the last item of heap follows the reducing the size of the heap by the 1. Now the just heapify the root of tree

3. while size of heap is greater than 1 just repeat above steps

How to execute this heap using javascript?

Lets us see an example

HTML CODE

</body>

</html>

JS CODE

               var heapSort = function(array) {
  var swap = function(array, firstIndex, secondIndex) {
    var temp = array[firstIndex];
    array[firstIndex] = array[secondIndex];
    array[secondIndex] = temp;
  };
  var maxHeap = function(array, i) {
    var l = 2 * i;
    var r = l + 1;
    var largest;
    if (l < array.heapSize && array[l] > array[i]) {
      largest = l;
    } else {
      largest = i;
    }
    if (r < array.heapSize && array[r] > array[largest]) {
      largest = r;
    }
    if (largest != i) {
      swap(array, i, largest);
      maxHeap(array, largest);
    }
  };
  var buildHeap = function(array) {
    array.heapSize = array.length;
    for (var i = Math.floor(array.length / 2); i >= 0; i--) {
      maxHeap(array, i);
    }
  };
  buildHeap(array);
  for (var i = array.length-1; i >= 1; i--) {
    swap(array, 0, i);
    array.heapSize--;
    maxHeap(array, 0);
      
    document.getElementById("getHeapSort").innerHTML = document.getElementById("getHeapSort").innerHTML + a + "
";
  }
};
var a = [6, 5, 3, 1, 8, 7, 2, 4];
document.getElementById("getHeapSort").innerHTML = a + "
";
heapSort(a);

OUTPUT

6,5,3,1,8,7,2,4
7,6,5,4,3,1,2,8
6,5,3,4,2,1,7,8
5,4,3,1,2,6,7,8
4,3,2,1,5,6,7,8
3,2,1,4,5,6,7,8
2,1,3,4,5,6,7,8
1,2,3,4,5,6,7,8