Max Heap (Implementation)
How is Max-Heap implemented in Java? Let's find out in this lesson.
We'll cover the following...
Implementation
Now that we have discussed the important Max Heap functions, let’s move on to implementing them in Java.
Java
import java.util.Arrays;class Heap {private void maxHeapify(int[] heapArray, int index, int heapSize){int largest = index;while (largest < heapSize / 2){ // check parent nodes onlyint left = (2 * index) + 1; //left childint right = (2 * index) + 2; //right childif (left < heapSize && heapArray[left] > heapArray[index]){largest = left;}if (right < heapSize && heapArray[right] > heapArray[largest]){largest = right;}if (largest != index){ // swap parent with largest childint temp = heapArray[index];heapArray[index] = heapArray[largest];heapArray[largest] = temp;index = largest;}elsebreak; // if heap property is satisfied} //end of while}public void buildMaxHeap(int[] heapArray, int heapSize){// swap largest child to parent nodefor (int i = (heapSize - 1) / 2; i >= 0; i--){maxHeapify(heapArray, i, heapSize);}}public static void main(String[] args) {int[] heapArray = { 1, 4, 7, 12, 15, 14, 9, 2, 3, 16 };System.out.println("Before heapify: "+Arrays.toString(heapArray));new Heap().buildMaxHeap(heapArray, heapArray.length);System.out.println("After heapify: "+Arrays.toString(heapArray));}}
Explanation
This code covers all the cases that we discussed in the previous chapter. Let’s look at each function one by one and see what’s going on:
-
BuildHeap(): It takes the array and starts from the last parent node at the second last level, then passes it to MaxHeapify for comparison.
-
MaxHeapify(): This function takes the node index and compares it with the key at the child node, and swaps them if the condition below stands
true.
...