Saturday 22 August 2015

Program to build min heap

Min Heap

In a min heap, the keys of parent nodes are always less than or equal to those of the children and the lowest key is in the root node.
How to construct a Min heap
Following video explains about min heap clearly.
import java.util.Objects;

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

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

  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] < arr[temp])
   temp = left;

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

  if (temp == position)
   return;

  swap(position, temp);
  minHeap(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.

import static org.junit.Assert.assertTrue;

import java.util.Arrays;

import org.junit.Test;

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

  minHeap.buildMinHeap(arr1);
  minHeap.buildMinHeap(arr2);
  minHeap.buildMinHeap(arr3);
  minHeap.buildMinHeap(arr4);
  minHeap.buildMinHeap(arr5);
  minHeap.buildMinHeap(arr6);
  minHeap.buildMinHeap(arr7);
  minHeap.buildMinHeap(arr8);
  minHeap.buildMinHeap(arr9);
  minHeap.buildMinHeap(arr10);

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






No comments:

Post a Comment