Search⌘ K
AI Features

Min Heap (Implementation)

Explore the implementation of a Min Heap in Java, including key operations like BuildHeap and MinHeapify. This lesson helps you understand how the heap property is maintained through node comparisons and swaps, preparing you for coding interviews focused on heap data structures.

Implementation

Let’s implement different scenarios of a Min Heap in the following code. Run and test the code on multiple outputs to see if it returns the elements in correct order every time? Try it!

Java
import java.util.Arrays;
class Heap {
private void minHeapify(int[] heapArray, int index, int heapSize) {
int smallest = index;
while (smallest < 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]) {
smallest = left;
}
if (right < heapSize && heapArray[right] < heapArray[smallest]) {
smallest = right;
}
if (smallest != index) { // swap parent with smallest child
int temp = heapArray[index];
heapArray[index] = heapArray[smallest];
heapArray[smallest] = temp;
index = smallest;
} else {
break; // if heap property is satisfied
}
} //end of while
}
public void buildMinHeap(int[] heapArray, int heapSize) {
// swap smallest child to parent node
for (int i = (heapSize - 1) / 2; i >= 0; i--) {
minHeapify(heapArray, i, heapSize);
}
}
public static void main(String[] args) {
int[] heapArray = { 31, 11, 7, 12, 15, 14, 9, 2, 3, 16 };
System.out.println("Before heapify: "+Arrays.toString(heapArray));
new Heap().buildMinHeap(heapArray, heapArray.length);
System.out.println("After heapify: "+Arrays.toString(heapArray));
}
}

Explanation:

This code covers all the cases. Let’s look at each function one by one and see what’s going on:

  • BuildHeap(): It takes the array and starts from
...