Program to build max heap

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.

Example

Following video explains about max heap clearly.

https://www.youtube.com/watch?v=WsNQuCa_-PU

import java.util.Objects;

public class MaxHeap {
 private int arr[];
 private int length;

 public void buildMaxHeap(int arr[]) {
  Objects.nonNull(arr);
  int start = arr.length / 2;
  this.arr = arr;
  length = arr.length;

  for (int i = start - 1; i > -1; i--) {
   maxHeap(i);
  }
 }

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

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

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

  if (temp == position)
   return;

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

 private void swap(int i, int j) {
  int 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 MaxHeapTest {

 @Test
 public void test1() {
  MaxHeap maxHeap = new MaxHeap();
  int arr1[] = { 1 };
  int arr2[] = { 1, 2 };
  int arr3[] = { 1, 2, 3 };
  int arr4[] = { 1, 2, 3, 4 };
  int arr5[] = { 1, 2, 3, 4, 5 };
  int arr6[] = { 1, 2, 3, 4, 5, 6 };
  int arr7[] = { 1, 2, 3, 4, 5, 6, 7 };
  int arr8[] = { 1, 2, 3, 4, 5, 6, 7, 8 };
  int arr9[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
  int arr10[] = { 9, 8, 7, 6, 5, 4, 3, 2, 1, 0 };

  maxHeap.buildMaxHeap(arr1);
  maxHeap.buildMaxHeap(arr2);
  maxHeap.buildMaxHeap(arr3);
  maxHeap.buildMaxHeap(arr4);
  maxHeap.buildMaxHeap(arr5);
  maxHeap.buildMaxHeap(arr6);
  maxHeap.buildMaxHeap(arr7);
  maxHeap.buildMaxHeap(arr8);
  maxHeap.buildMaxHeap(arr9);
  maxHeap.buildMaxHeap(arr10);

  assertTrue(Arrays.equals(arr1, new int[] { 1 }));
  assertTrue(Arrays.equals(arr2, new int[] { 2, 1 }));
  assertTrue(Arrays.equals(arr3, new int[] { 3, 2, 1 }));
  assertTrue(Arrays.equals(arr4, new int[] { 4, 2, 3, 1 }));
  assertTrue(Arrays.equals(arr5, new int[] { 5, 4, 3, 1, 2 }));
  assertTrue(Arrays.equals(arr6, new int[] { 6, 5, 3, 4, 2, 1 }));
  assertTrue(Arrays.equals(arr7, new int[] { 7, 5, 6, 4, 2, 1, 3 }));
  assertTrue(Arrays.equals(arr8, new int[] { 8, 5, 7, 4, 1, 6, 3, 2 }));
  assertTrue(Arrays.equals(arr9, new int[] { 9, 8, 7, 4, 5, 6, 3, 2, 1 }));
  assertTrue(Arrays.equals(arr10, new int[] { 9, 8, 7, 6, 5, 4, 3, 2, 1,
    0 }));
 }
}