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.
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
.
The while loop makes sure that the nodes keep swapping until the Heap property is satisfied, so we basically call MaxHeapify();
at each small level to achieve Max Heap.
If this Code had a Face
Time Complexity
The worst-case time complexity of maxHeapify()
is because we start with the rightmost leaf node in the heap, then move left and then up until we reach the root node.
In buildMaxHeap()
, the heapify function is called times. Therefore, the overall time ...