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