...

/

Max Heap (Implementation)

Max Heap (Implementation)

How is Max-Heap implemented in Java? Let's find out in this lesson.

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 only
int left = (2 * index) + 1; //left child
int right = (2 * index) + 2; //right child
if (left < heapSize && heapArray[left] > heapArray[index]){
largest = left;
}
if (right < heapSize && heapArray[right] > heapArray[largest]){
largest = right;
}
if (largest != index){ // swap parent with largest child
int temp = heapArray[index];
heapArray[index] = heapArray[largest];
heapArray[largest] = temp;
index = largest;
}
else
break; // if heap property is satisfied
} //end of while
}
public void buildMaxHeap(int[] heapArray, int heapSize)
{
// swap largest child to parent node
for (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.

ChildNode>=ParentNodeChild Node >= ParentNode

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 O(lgn)O(lgn) 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 O(n)O(n) times. Therefore, the overall time ...