Merge pull request thuva4#113 from Decoys-out/Heap-Sort

thuva4 · web-flow · commit 5ec8752c76be · 2017-10-06T07:53:44.000+05:30
Added Heapsort
diff --git a/HeapSort/JavaScript/heapsort.js b/HeapSort/JavaScript/heapsort.js
@@ -0,0 +1,59 @@
+/*
+* Build a max heap out of the array. A heap is a specialized tree like
+* data structure that satisfies the heap property. The heap property
+* for max heap is the following: "if P is a parent node of C, then the
+* key (the value) of node P is greater than the key of node C"
+* Source: https://en.wikipedia.org/wiki/Heap_(data_structure)
+*/
+Array.prototype.heapify = function (index, heapSize) {
+
+  var largest = index;
+  var leftIndex = 2 * index + 1;
+  var rightIndex = 2 * index + 2;
+
+  if (leftIndex < heapSize && this[leftIndex] > this[largest]) {
+    largest = leftIndex;
+  }
+
+  if (rightIndex < heapSize && this[rightIndex] > this[largest]) {
+    largest = rightIndex;
+  }
+
+  if (largest !== index) {
+    var temp = this[largest];
+    this[largest] = this[index];
+    this[index] = temp;
+
+    this.heapify(largest, heapSize);
+  }
+};
+
+/*
+* Heap sort sorts an array by building a heap from the array and
+* utilizing the heap property.
+* For more information see: https://en.wikipedia.org/wiki/Heapsort
+*/
+function heapSort(items) {
+
+  var length = items.length;
+
+  for (var i = Math.floor(items.length / 2) - 1; i > -1; i--) {
+    items.heapify(i, length);
+  }
+  for (var j = length -1; j > 0; j--) {
+    var tmp = items[0];
+    items[0] = items[j];
+    items[j] = tmp;
+    items.heapify(0, j);
+  }
+  return items;
+}
+
+//Implementation of heapSort
+
+var ar = [5, 6, 7, 8, 1, 2, 12, 14];
+//Array before Sort
+console.log(ar);
+heapSort(ar);
+//Array after sort
+console.log(ar);
