TheAlgorithms · debasishbsws · Nov 25, 2022 · Oct 6, 2022 · Oct 21, 2022 · Oct 21, 2022
@@ -1,126 +1,56 @@
 package com.thealgorithms.sorts;
 
-import static com.thealgorithms.sorts.SortUtils.*;
-
-import java.util.ArrayList;
-import java.util.Arrays;
-import java.util.List;
-
 /**
- * Heap Sort Algorithm Implements MinHeap
+ * Heap Sort Algorithm Implementation
  *
- * @author Podshivalov Nikita (https://github.com/nikitap492)
+ * @see <a href="https://en.wikipedia.org/wiki/Heapsort">Heap Sort Algorithm</a>
  */
 public class HeapSort implements SortAlgorithm {
 
-    private static class Heap<T extends Comparable<T>> {
-
-        /**
-         * Array to store heap
-         */
-        private T[] heap;
-
-        /**
-         * Constructor
-         *
-         * @param heap array of unordered integers
-         */
-        public Heap(T[] heap) {
-            this.heap = heap;
+    /**
+     * For simplicity, we are considering the heap root index as 1 instead of 0.
+     * It simplifies future calculations. Because of that we are decreasing the
+     * provided indexes by 1 in {@link #swap(Object[], int, int)} and
+     * {@link #less(Comparable[], int, int)} functions.
+     */
+    @Override
+    public <T extends Comparable<T>> T[] sort(T[] unsorted) {
+        int n = unsorted.length;
+        heapify(unsorted, n);
+        while (n > 1) {
+            swap(unsorted, 1, n--);
+            siftDown(unsorted, 1, n);
         }
+        return unsorted;
+    }
 
-        /**
-         * Heapifies subtree from top as root to last as last child
-         *
-         * @param rootIndex index of root
-         * @param lastChild index of last child
-         */
-        private void heapSubtree(int rootIndex, int lastChild) {
-            int leftIndex = rootIndex * 2 + 1;
-            int rightIndex = rootIndex * 2 + 2;
-            T root = heap[rootIndex];
-            if (rightIndex <= lastChild) { // if has right and left children
-                T left = heap[leftIndex];
-                T right = heap[rightIndex];
-                if (less(left, right) && less(left, root)) {
-                    swap(heap, leftIndex, rootIndex);
-                    heapSubtree(leftIndex, lastChild);
-                } else if (less(right, root)) {
-                    swap(heap, rightIndex, rootIndex);
-                    heapSubtree(rightIndex, lastChild);
-                }
-            } else if (leftIndex <= lastChild) { // if no right child, but has left child
-                T left = heap[leftIndex];
-                if (less(left, root)) {
-                    swap(heap, leftIndex, rootIndex);
-                    heapSubtree(leftIndex, lastChild);
-                }
-            }
+    private static <T extends Comparable<T>> void heapify(T[] unsorted, int n) {
+        for (int k = n / 2; k >= 1; k--) {
+            siftDown(unsorted, k, n);
         }
+    }
 
-        /**
-         * Makes heap with root as root
-         *
-         * @param root index of root of heap
-         */
-        private void makeMinHeap(int root) {
-            int leftIndex = root * 2 + 1;
-            int rightIndex = root * 2 + 2;
-            boolean hasLeftChild = leftIndex < heap.length;
-            boolean hasRightChild = rightIndex < heap.length;
-            if (hasRightChild) { // if has left and right
-                makeMinHeap(leftIndex);
-                makeMinHeap(rightIndex);
-                heapSubtree(root, heap.length - 1);
-            } else if (hasLeftChild) {
-                heapSubtree(root, heap.length - 1);
+    private static <T extends Comparable<T>> void siftDown(T[] unsorted, int k, int n) {
+        while (2 * k <= n) {
+            int j = 2 * k;
+            if (j < n && less(unsorted, j, j + 1)) {
+                j++;
             }
+            if (!less(unsorted, k, j)) {
+                break;
+            }
+            swap(unsorted, k, j);
+            k = j;
         }
-
-        /**
-         * Gets the root of heap
-         *
-         * @return root of heap
-         */
-        private T getRoot(int size) {
-            swap(heap, 0, size);
-            heapSubtree(0, size - 1);
-            return heap[size]; // return old root
-        }
-    }
-
-    @Override
-    public <T extends Comparable<T>> T[] sort(T[] unsorted) {
-        return sort(Arrays.asList(unsorted)).toArray(unsorted);
     }
 
-    @Override
-    public <T extends Comparable<T>> List<T> sort(List<T> unsorted) {
-        int size = unsorted.size();
-
-        @SuppressWarnings("unchecked")
-        Heap<T> heap = new Heap<>(
-            unsorted.toArray((T[]) new Comparable[unsorted.size()])
-        );
-
-        heap.makeMinHeap(0); // make min heap using index 0 as root.
-        List<T> sorted = new ArrayList<>(size);
-        while (size > 0) {
-            T min = heap.getRoot(--size);
-            sorted.add(min);
-        }
-
-        return sorted;
+    private static <T> void swap(T[] array, int idx, int idy) {
+        T swap = array[idx - 1];
+        array[idx - 1] = array[idy - 1];
+        array[idy - 1] = swap;
     }
 
-    /**
-     * Main method
-     *
-     * @param args the command line arguments
-     */
-    public static void main(String[] args) {
-        Integer[] heap = { 4, 23, 6, 78, 1, 54, 231, 9, 12 };
-        HeapSort heapSort = new HeapSort();
-        print(heapSort.sort(heap));
+    private static <T extends Comparable<T>> boolean less(T[] array, int idx, int idy) {
+        return array[idx - 1].compareTo(array[idy - 1]) < 0;
     }
 }
@@ -1,35 +1,95 @@
 package com.thealgorithms.sorts;
 
 import static org.junit.jupiter.api.Assertions.assertArrayEquals;
+import static org.junit.jupiter.api.Assertions.assertTrue;
 
+import org.junit.jupiter.api.BeforeEach;
 import org.junit.jupiter.api.Test;
 
 public class HeapSortTest {
-
-	private HeapSort heapSort = new HeapSort();
-
-	@Test
-    void testHeapSortCase1() {
-        Integer[] array = { 49, 4, 36, 9, 144, 1 };
+    private HeapSort heapSort;
+
+    @BeforeEach
+    void setUp() {
+        heapSort = new HeapSort();
+    }
+
+    @Test
+    void shouldAcceptWhenEmptyArrayIsPassed() {
+        Integer[] array = new Integer[]{};
+        Integer[] expected = new Integer[]{};
+
+        Integer[] sorted = heapSort.sort(array);
+
+        assertArrayEquals(expected, sorted);
+    }
+
+    @Test
+    void shouldAcceptWhenSingleValuedArrayIsPassed() {
+        Integer[] array = new Integer[]{2};
+        Integer[] expected = new Integer[]{2};
+
+        Integer[] sorted = heapSort.sort(array);
+
+        assertArrayEquals(expected, sorted);
+    }
+
+    @Test
+    void shouldAcceptWhenArrayWithAllPositiveValuesIsPassed() {
+        Integer[] array = new Integer[]{60, 7, 55, 9, 999, 3};
+        Integer[] expected = new Integer[]{3, 7, 9, 55, 60, 999};
+
+        Integer[] sorted = heapSort.sort(array);
+
+        assertArrayEquals(expected, sorted);
+    }
+
+    @Test
+    void shouldAcceptWhenArrayWithAllNegativeValuesIsPassed() {
+        Integer[] array = new Integer[]{-60, -7, -55, -9, -999, -3};
+        Integer[] expected = new Integer[]{-999, -60, -55, -9, -7, -3};
+
         Integer[] sorted = heapSort.sort(array);
-        Integer[] expected = { 1, 4, 9, 36, 49, 144 };
+
         assertArrayEquals(expected, sorted);
     }
-
-	@Test
-    void testHeapSortCase2() {
-        Integer[] array = { };
+
+    @Test
+    void shouldAcceptWhenArrayWithRealNumberValuesIsPassed() {
+        Integer[] array = new Integer[]{60, -7, 55, 9, -999, -3};
+        Integer[] expected = new Integer[]{-999, -7, -3, 9, 55, 60};
+
         Integer[] sorted = heapSort.sort(array);
-        Integer[] expected = { };
+
         assertArrayEquals(expected, sorted);
     }
-
-	@Test
-    void testHeapSortCase3 () {
-        Integer[] array = { -3, 5, 3, 4, 3, 7, 40, -20, 30, 0 };
+
+    @Test
+    void shouldAcceptWhenArrayWithDuplicateValueIsPassed() {
+        Integer[] array = new Integer[]{60, 7, 55, 55, 999, 3};
+        Integer[] expected = new Integer[]{3, 7, 55, 55, 60, 999};
+
         Integer[] sorted = heapSort.sort(array);
-        Integer[] expected = { -20, -3, 0, 3, 3, 4, 5, 7, 30, 40 };
+
         assertArrayEquals(expected, sorted);
     }
 
+    @Test
+    void shouldAcceptWhenStringValueArrayIsPassed() {
+        String[] array = {"z", "a", "x", "b", "y"};
+        String[] expected = {"a", "b", "x", "y", "z"};
+
+        String[] sorted = heapSort.sort(array);
+
+        assertArrayEquals(expected, sorted);
+    }
+
+    @Test
+    void shouldAcceptWhenRandomArrayIsPassed() {
+        int randomSize = SortUtilsRandomGenerator.generateInt(10_000);
+        Double[] array = SortUtilsRandomGenerator.generateArray(randomSize);
+        Double[] sorted = heapSort.sort(array);
+        assertTrue(SortUtils.isSorted(sorted));
+    }
+
 }