...

/

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.

...