Min Heap (Implementation)
How is a Min Heap implemented in Java? Let's find out in this lesson.
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!
Press + to interact
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