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
- getMin(): It returns the root element of Min Heap. Time Complexity of this operation is O(1).
- 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.
- 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[]) {
// Adding elements using add()
minHeap.add(8);
minHeap.add(5);
minHeap.add(13);
minHeap.add(2);
minHeap.add(23);
minHeap.add(16);
// Displaying minHeap elements
print();
// Find number of elements using size()
System.out.println("Size of heap = "+minHeap.size());
// View head using peek()
System.out.println("Head = "+minHeap.peek());
// Remove head and modify Heap using poll()
minHeap.poll();
System.out.println("Heap after removing head");
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
Head = 2
Heap after removing head
Min Heap : 5 8 13 16 23
Heap after removing 8
Min Heap : 5 16 13 23
Top comments (0)