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.
Press + to interact
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
.
...