Min Heap (Implementation)
How is a Min Heap implemented in Java? Let's find out in this lesson.
We'll cover the following...
We'll cover the following...
Implementation
Let’s implement different scenarios of a Min Heap in the following code. Run and test the code on multiple outputs to see if it returns the elements in correct order every time? Try it!
Java
import java.util.Arrays;class Heap {private void minHeapify(int[] heapArray, int index, int heapSize) {int smallest = index;while (smallest < heapSize / 2) { // check parent nodes onlyint left = (2 * index) + 1; //left childint right = (2 * index) + 2; //right childif (left < heapSize && heapArray[left] < heapArray[index]) {smallest = left;}if (right < heapSize && heapArray[right] < heapArray[smallest]) {smallest = right;}if (smallest != index) { // swap parent with smallest childint temp = heapArray[index];heapArray[index] = heapArray[smallest];heapArray[smallest] = temp;index = smallest;} else {break; // if heap property is satisfied}} //end of while}public void buildMinHeap(int[] heapArray, int heapSize) {// swap smallest child to parent nodefor (int i = (heapSize - 1) / 2; i >= 0; i--) {minHeapify(heapArray, i, heapSize);}}public static void main(String[] args) {int[] heapArray = { 31, 11, 7, 12, 15, 14, 9, 2, 3, 16 };System.out.println("Before heapify: "+Arrays.toString(heapArray));new Heap().buildMinHeap(heapArray, heapArray.length);System.out.println("After heapify: "+Arrays.toString(heapArray));}}
Explanation:
This code covers all the cases. Let’s look at each function one by one and see what’s going on:
- BuildHeap(): It takes the array and starts from