Heap sort Java

Heap sorts sort the elements based on heap data structure.

Heap is a tree kind of data structure that satisfies heap property. There are two kinds of heaps.

Max Heap

In a max heap, the keys of parent nodes are always greater than or equal to those of the children and the highest key is in the root node.

How to construct max heap

Following link explains it clearly.

Build Max Heap

Example

Min Heap

In a min heap, the keys of parent nodes are always greater than or equal to those of the children and the lowest key is in the root node.

How to construct a Min heap

Following link explains it clearly.

Build Min Heap

Sorting elements in ascending order

Step 1: Build max heap.

Step 2: Swap element at 0^th position with last element of the array.

Step 3: Decrement the length of the array.

Step 4: Call maxHeap method on element 0. Repeat steps2 to 3 until length of array > 0.

import java.util.Objects;

public class HeapSort<T extends Comparable<T>> {
 private T arr[];
 private int length;

 /**
  * If flag is true, then elements are sorted in ascending order, else
  * descending order
  */
 public void sort(T[] arr, boolean flag) {
  Objects.nonNull(arr);
  this.arr = arr;
  length = arr.length;

  if (flag == true)
   sortAscending(arr);
  else
   sortDescending(arr);
 }

 private void sortDescending(T arr[]) {
  buildMinHeap();
  swap(0, length - 1);
  length--;

  while (length > 0) {
   minHeap(0);
   swap(0, length - 1);
   length--;
  }
 }

 private void sortAscending(T arr[]) {
  buildMaxHeap();
  swap(0, length - 1);
  length--;

  while (length > 0) {
   maxHeap(0);
   swap(0, length - 1);
   length--;
  }

 }

 private void buildMaxHeap() {
  int start = length / 2;
  for (int i = start - 1; i > -1; i--) {
   maxHeap(i);
  }
 }

 private void buildMinHeap() {
  int start = length / 2;
  for (int i = start - 1; i > -1; i--) {
   minHeap(i);
  }
 }

 private void minHeap(int position) {
  int left = 2 * position + 1;
  int right = left + 1;
  int temp = position;

  if (left < length && arr[left].compareTo(arr[temp]) < 0)
   temp = left;

  if (right < length && arr[right].compareTo(arr[temp]) < 0)
   temp = right;

  if (temp == position)
   return;

  swap(position, temp);
  minHeap(temp);
 }

 private void maxHeap(int position) {
  int left = 2 * position + 1;
  int right = left + 1;
  int temp = position;

  if (left < length && arr[left].compareTo(arr[temp]) > 0)
   temp = left;

  if (right < length && arr[right].compareTo(arr[temp]) > 0)
   temp = right;

  if (temp == position)
   return;

  swap(position, temp);
  maxHeap(temp);
 }

 private void swap(int i, int j) {
  T temp = arr[i];
  arr[i] = arr[j];
  arr[j] = temp;
 }
}

Following is the junit test case for above program.

import static org.junit.Assert.assertTrue;

import java.util.Arrays;

import org.junit.Test;

public class HeapSortTest {

 @Test
 public void test1() {
  HeapSort<Integer> heapSort = new HeapSort<>();
  Integer arr1[] = { 2, 4, 6, 8, 1, 3, 5, 7 };
  Integer arr2[] = { 5, 46, 25, 13, 12 };
  Integer arr3[] = { 5, 46 };

  heapSort.sort(arr1, true);
  assertTrue(Arrays
    .equals(arr1, new Integer[] { 1, 2, 3, 4, 5, 6, 7, 8 }));

  heapSort.sort(arr1, false);
  assertTrue(Arrays
    .equals(arr1, new Integer[] { 8, 7, 6, 5, 4, 3, 2, 1 }));

  heapSort.sort(arr2, true);
  assertTrue(Arrays.equals(arr2, new Integer[] { 5, 12, 13, 25, 46 }));

  heapSort.sort(arr2, false);
  assertTrue(Arrays.equals(arr2, new Integer[] { 46, 25, 13, 12, 5 }));

  heapSort.sort(arr3, true);
  assertTrue(Arrays.equals(arr3, new Integer[] { 5, 46 }));

  heapSort.sort(arr3, false);
  assertTrue(Arrays.equals(arr3, new Integer[] { 46, 5 }));
 }
}