Add HeapSort in Java

ldhnam · ldhnam · commit bae8c1823704 · 2017-10-04T15:07:41.000+07:00
diff --git a/HeapSort/Java/HeapSort.java b/HeapSort/Java/HeapSort.java
@@ -0,0 +1,68 @@
+package com.dev.namhoai.sort;
+
+public class HeapSort {
+
+    public void sort(int[] arr) {
+        for (int i = 1; i < arr.length; i++) {
+            heapAdd(arr, i);
+        }
+
+        for (int i = arr.length - 1; i > 0; i--) {
+            swap(arr, 0, i);
+            heapify(arr, i - 1);
+        }
+    }
+
+    private void heapify(int[] arr, int end) {
+        int i = 0;
+        int leftIndex;
+        int rightIndex;
+        while (i <= end) {
+            leftIndex = 2 * i + 1;
+            if (leftIndex > end) {
+                break;
+            }
+            rightIndex = 2 * i + 2;
+            if (rightIndex > end) {
+                rightIndex = leftIndex;
+            }
+            if (arr[i] >= Math.max(arr[leftIndex], arr[rightIndex])) {
+                break;
+            }
+            if (arr[leftIndex] >= arr[rightIndex]) {
+                swap(arr, i, leftIndex);
+                i = leftIndex;
+            } else {
+                swap(arr, i, rightIndex);
+                i = rightIndex;
+            }
+        }
+    }
+
+    private void swap(int[] arr, int x, int y) {
+        int temp = arr[x];
+        arr[x] = arr[y];
+        arr[y] = temp;
+    }
+
+    private void heapAdd(int[] arr, int end) {
+        int i = end;
+        while (i > 0) {
+            if (arr[i] > arr[(i - 1) / 2]) {
+                swap(arr, i, (i - 1) / 2);
+                i = (i - 1) / 2;
+            } else {
+                break;
+            }
+        }
+    }
+
+    public static void main(String[] args) {
+        HeapSort hs = new HeapSort();
+        int[] arr = {-1, 5, 8, 2, -6, -8, 11, 5};
+        hs.sort(arr);
+        for (int a : arr) {
+            System.out.println(a);
+        }
+    }
+}
