AI Features

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.

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 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.

ChildNod ...