Search⌘ K
AI Features

Max Heap (Implementation)

Explore how to implement a Max Heap in Java by understanding BuildHeap and MaxHeapify functions. Learn the step-by-step process and analyze the time complexity of building and maintaining the heap structure to strengthen your data structure skills for coding interviews.

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