Add Heap Sort

dipyamansaha · web-flow · commit f07a78fb6ff4 · 2020-10-31T12:36:41.000+05:30
diff --git a/HeapSortAlgo.java b/HeapSortAlgo.java
@@ -0,0 +1,69 @@
+import java.util.Arrays;
+import java.util.Scanner;
+
+/**
+ * @author Dipyaman Saha (https://github.com/dipyamansaha) - HEAP SORT ALGORITHM -
+ *     https://en.wikipedia.org/wiki/Heapsort
+ */
+public class HeapSortAlgo {
+  static void HeapSort(int[] Arr) {
+    int n = Arr.length;
+
+    BuildMaxHeap(Arr);
+
+    for (int i = (n - 1); i >= 0; i--) {
+      int temp = Arr[0];
+      Arr[0] = Arr[i];
+      Arr[i] = temp;
+
+      MaxHeapify(Arr, i, 0);
+    }
+  }
+
+  static void MaxHeapify(int[] Arr, int n, int i) {
+    int l = (2 * i + 1);
+    int r = (2 * i + 2);
+
+    int largest;
+
+    if ((l < n) && (Arr[l] > Arr[i])) largest = l;
+    else largest = i;
+
+    if ((r < n) && (Arr[r] > Arr[largest])) largest = r;
+
+    if (largest != i) {
+      int temp = Arr[i];
+      Arr[i] = Arr[largest];
+      Arr[largest] = temp;
+
+      MaxHeapify(Arr, n, largest);
+    }
+  }
+
+  static void BuildMaxHeap(int[] Arr) {
+    int n = Arr.length;
+
+    for (int i = (n / 2 - 1); i >= 0; i--) MaxHeapify(Arr, n, i);
+  }
+
+  public static void main(String[] args) {
+    System.out.println("HEAP SORT ALGORITHM\n");
+
+    Scanner sc = new Scanner(System.in);
+
+    System.out.print("How many elements do you wanna insert? ");
+    int n = sc.nextInt();
+
+    int[] Arr = new int[n];
+
+    System.out.println("Enter the elements: ");
+    for (int i = 0; i < n; i++) {
+      Arr[i] = sc.nextInt();
+    }
+
+    System.out.println("The entered array: " + Arrays.toString(Arr));
+
+    HeapSort(Arr);
+    System.out.println("The sorted array: " + Arrays.toString(Arr));
+  }
+}
