Shashi Preetham

Posted on

# Implementing Min Heap in Java

A Min-Heap is a complete binary tree in which the value in each internal node is smaller than or equal to the values in the children of that node.

Mapping the elements of a heap into an array is trivial: if a node is stored an index n, then its left child is stored at index 2n+1 and its right child at index 2n+2.

### Example

#### Min Heap Representation

A Min heap is typically represented as an array.
Consider an array `Arr[]` with root at `Arr[0]`. For any ith node, i.e., Arr[i]:

• `Arr[(i -1) / 2]` returns its parent node.
• `Arr[(2 * i) + 1]` returns its left child node.
• `Arr[(2 * i) + 2]` returns its right child node.

#### Operations on Min Heap

1. getMin(): It returns the root element of Min Heap. Time Complexity of this operation is O(1).
2. extractMin(): Removes the minimum element from MinHeap. Time Complexity of this Operation is O(Log n) as this operation needs to maintain the heap property (by calling heapify()) after removing root.
3. insert(): Inserting a new key takes O(Log n) time. We add a new key at the end of the tree. If new key is larger than its parent, then we don’t need to do anything. Otherwise, we need to traverse up to fix the violated heap property.

#### Implementation of Min Heap in Java using Priority Queues

Here’s how you can implement a min heap using `PriorityQueue` class in Java. By default Min Heap is implemented by this class.

``````import java.util.*;
public class MinHeap {
static PriorityQueue<Integer> minHeap = new PriorityQueue<Integer>();
public static void main(String args[]) {

// Displaying minHeap elements
print();

// Find number of elements using size()
System.out.println("Size of heap = "+minHeap.size());

// Remove head and modify Heap using poll()
minHeap.poll();
print();

// Remove specific element using remove()
minHeap.remove(8);
System.out.println("Heap after removing 8");
print();

// Check if an element is present using contains()
boolean flag=minHeap.contains(15);
System.out.println("Does heap contain element 15? " +flag);

System.out.println("Size of heap = "+minHeap.size());
}
public static void print() {
System.out.print("Min Heap : ");
for(Integer i:minHeap)
System.out.print(i+" ");
System.out.println("\n");
}
}
``````

Output

``````Min Heap : 2 5 13 8 23 16

Size of heap = 6