Min Heap in Java

Last Updated on December 14, 2022 by Prepbytes

What is Heap?

Heap is a special kind of complete binary tree in which the all node has a value greater
(or smaller ) than all of its children .

A complete binary tree is a binary tree where all levels are completely filled except the last level which can be complete or incomplete . All nodes should be filled from left to right .

There are two types of heap , [Min heap](https://www.prepbytes.com/blog/heap/min-heappaid/ “Min heap”) and Max heap . In Max heap all nodes have value greater than the children’s value whereas in Min heap all nodes have value smaller than the children’s value .

In this Article we will focus on Min heap only .

What is Min-heap?

A Heap in which all nodes have a value smaller than all its children , is [Min heap](https://www.prepbytes.com/blog/heap/min-heappaid/ “Min heap”) .
i.e for a node its value is less than the value of its left child and the value of its right child and this property is recursively true for every node .In other words , we can also say that any node
at a certain level has less value than all nodes below its level.

Representation of Min-heap

1. A Min heap is represented using an Array .
2. A node at i-th position has its left child at 2 i+1 and right child at 2 i+2 .
3. A node at i-th position has its parent at (i-1)/2 .
4. In min heap , heap[i] < heap[2 i+1] and heap[i] < heap[2 i+2]

Node at position 0 has left child at 20+1 = 1 and right child at 2 0+2 = 2 positions .
Value of node at 0 is smaller than the value of nodes at 1 and 2.

Node at position 1 has left child at 2 1+1 = 3 and right child at 2 1+2 = 4 positions .

Node at position 2 has only left child at position 2 * 2+1=5 .

Nodes at position 3,4 and 5 are leaf nodes with no child .

Operations on Min heap

getMin() : This method will return the minimum number in the heap .

deleteMin() : The method will delete the node with minimum value .Following steps are taken in this method :

1. Swap root node with the rightmost node .
2. Delete rightmost node
3. Call heapify method for root
   Because of heapify() , the time complexity of this method is O(logn) .

heapify() : This will be the private method for the MinHeap class . The method ensures that heap property is maintained .

insert() : The method is used to insert new nodes in the min heap . A new node is inserted at the end of the heap array , and we keep on swapping this node with the parent node if it is violating heap property .

size() : returns size of heap.

Time complexity of all operations is O(logn) except getMin() and size().

Implementation of Min heap in Java

Implementation of Min heap using java libraries

We can also implement max heap using PriorityQueue class .By default it creates a min heap.

/* package whatever; // don't place package name! */

import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
class Ideone
{
	public static void main (String[] args) throws java.lang.Exception
	{
		// your code goes 
		PriorityQueue<Integer> heap = new PriorityQueue<Integer>();
        heap.add(11);
        heap.add(2);
        heap.add(10);
        heap.add(7);
        heap.add(3);
        heap.add(8);
        System.out.println("size of heap : " + heap.size());
        System.out.println("min in heap : " +heap.peek());
        heap.poll();
        System.out.println("after deletion");
        System.out.println("size of heap : " + heap.size());
        System.out.println("min in heap : " +heap.peek());
	}
}

This article tried to discuss Min heap in Java. Hope this blog helps you understand and solve the problem. To practice more problems you can check out MYCODE | Competitive Programming at Prepbytes