Min Heap in Java with Examples

Before we get started, it is assumed that you know about a Binary Tree (in a binary tree, each node stores a key greater than all the keys in its left subtree and less than all the keys in its right subtree). Whereas, a Binary Heap is a complete binary tree which satisfies either the min-heap or max-heap ordering property. If you’re not familiar with these concepts, we recommend you to understand these as a prerequisite. Many novice programmers can struggle with the concept of Heaps, Min Heaps and Priority Queues. In this post we’ll take a deep dive to see how heaps are different from Min-Heaps and how we can use Priority Queues to Implement Min Heaps.

What is a Min Heap?

A min-heap has the property that every node at level ‘n’ stores a value that is less than or equal to that of its children at level ‘n+1’. Because the root has a value less than or equal to its children, which in turn have values less than or equal to their children, the root stores the minimum of all values in the tree.

Example

Figure 1: A simple min heap Note that there is no necessary relationship between the value of a node and that of its sibling in either the min-heap or the max-heap. For example, it is possible that the values for all nodes in the left subtree of the root are greater than the values for every node of the right subtree.Figure 2: Min heap with left child nodes > right child nodes

Representation of Min Heap in Java

The most commonly used data structure to represent a Min Heap is a simple Array. As a beginner you do not need to confuse an “array” with a “min-heap”. You can look at it as, the values of nodes / elements of a min-heap are stored in an array. Just like we don’t have any data structure to store a “tree” in Java and we build a “node” for it, or the way we use “map” to store a “graph”.Figure 3: Array representation of the Heap in Figure 2 We are going to demonstrate how you can simply access the parent, right or left child nodes using the following formulas.

• Let minHeap[] is an integer array with root at index “i = 0;”.
• minHeap[(i - 1) / 2] returns the parent node.
• minHeap[(i * 2) + 2] returns the right child node.
• minHeap[(i * 2) + 1] returns the left child node.

Considering the Figure # 2 given above, the value of root (parent) = 3, left child node is 13 and right child node = 7.

Implementation of Min Heap in Java - Using Arrays

Let’s look at the basic implementation of Heaps using array, with index as the current position of the element to be added, and size as the total size of the array.

import java.util.Arrays;
public class MinHeap 
{
	private int[] Heap;
	private int index;
	private int size;

	public MinHeap(int size) {
		this.size = size;
		this.index = 0;
		Heap = new int[size];
	}

	private int parent(int i) {
		return (i - 1) / 2;
	}

	private int leftChild(int i) {
		return (i * 2) + 1;
	}

	private int rightChild(int i) {
		return (i * 2) + 2;
	}

	private boolean isLeaf(int i) {
		if (rightChild(i) >= size || leftChild(i) >= size) {
			return true;
		}
		return false;
	}

	public void insert(int element) {
		if (index >= size) {
			return;
		}
		Heap[index] = element;
		int current = index;

		while (Heap[current] < Heap[parent(current)]) {
			swap(current, parent(current));
			current = parent(current);
		}
		index++;
	}

	// removes and returns the minimum element from the heap
	public int remove() {
     // since its a min heap, so root = minimum
		int popped = Heap[0]; 
		Heap[0] = Heap[--index];
		minHeapify(0);
		return popped;
	}

	// heapify the node at i
	private void minHeapify(int i) {
	// If the node is a non-leaf node and any of its child is smaller
		if (!isLeaf(i)) {
			if (Heap[i] > Heap[leftChild(i)] || 
                  Heap[i] > Heap[rightChild(i)]) {
				if (Heap[leftChild(i)] < Heap[rightChild(i)]) {
					swap(i, leftChild(i));
					minHeapify(leftChild(i));
				} else {
					swap(i, rightChild(i));
					minHeapify(rightChild(i));
				}
			}
		}
	}

	// builds the min-heap using the minHeapify
	public void minHeap() {
		for (int i = (index - 1 / 2); i >= 1; i--) {
			minHeapify(i);
		}
	}

     // Function to print the contents of the heap
	public void printHeap() {
		for (int i = 0; i < (index / 2); i++) {
			System.out.print("Parent : " + Heap[i]);
			if (leftChild(i) < index)
				System.out.print(" Left : " + Heap[leftChild(i)]);
			if (rightChild(i) < index)
				System.out.print(" Right :" + Heap[rightChild(i)]);
			System.out.println();
		}
	}
	// swaps two nodes of the heap
	private void swap(int x, int y) {
		int tmp;
		tmp = Heap[x];
		Heap[x] = Heap[y];
		Heap[y] = tmp;
	}
	public static void main(String[] arg) 
      {
	    MinHeap minHeap = new MinHeap(7);
	    minHeap.insert(3);
	    minHeap.insert(13);
	    minHeap.insert(7);
          minHeap.insert(16);
	    minHeap.insert(21);
	    minHeap.insert(12);
	    minHeap.insert(9);
	    minHeap.minHeap();

	   System.out.println("The Min Heap is : " + Arrays.toString(minHeap.Heap);
	   minHeap.printHeap();
	   System.out.println("\nThe Min Value is : " + minHeap.remove());
	   System.out.println("\nThe Min Heap is :"+ Arrays.toString(minHeap.Heap));
	   minHeap.printHeap();
	}
}

Output

Priority Queues

A Priority Queue is a special type of queue in which each element is associated with a priority and is placed according to its priority. For an easier implementation of min heap, we use the PriorityQueue class java.util.PriorityQueue provided by Java. If the given elements are supposed to be sorted/placed in a priority then a Priority Queue is used. A Priority Queue is different from a simple Queue because the standard queues follow the First-In-First-Out (FIFO) algorithm, but sometimes the elements of the queue need to be processed according to the priority, that’s why Priority Queue is designed. When you add elements to a priority queue, a min heap is built by default.

Common Operations

Before we move on to the implementation here are a few common operations in java.util.PriorityQueue that you need to know.

• add(int element) inserts the specified element in a priority queue.
• remove(int element) removes a single instance of the specified element from this queue, if it is present.
• peek() retrieves, but does not remove, the head of this queue, or returns null if the queue is empty.
• poll() retrieves and removes the head of this queue, or returns null if this queue is empty.
• contains() returns “true” if this queue contains the specified element.
• size() returns the number of elements in this priority queue/minheap.

Implementation of Min Heap in Java using Priority Queues

Here’s how you can implement a min heap using priority queue class by java.

import java.util.*;

class MinHeapPriorityQueue {

	static PriorityQueue minHeap = new PriorityQueue();

	public static void view() {
		for (Integer x : minHeap) {
			System.out.print(x + " ");
		}
		System.out.println();
	}

	public static void main(String args[]) {
		// using "add" operation to insert elements
		minHeap.add(3);
		System.out.print("minHeap.add(3) = ");
		view();
		minHeap.add(13);
		minHeap.add(7);
		minHeap.add(16);
		minHeap.add(21);
		minHeap.add(12);
		minHeap.add(9);

		// printing Min-Heap
		System.out.print("minHeap.view() = ");
		view();

		// using "peek" method to view the head
		System.out.println("minHeap.peek() = " + minHeap.peek());

		// using "poll" method to remove and retrieve the head
		minHeap.poll();
		System.out.print("minHeap.poll() = ");
		view();

		// using "remove" method to remove specified element
		minHeap.remove(7);
		System.out.print("minHeap.remove(7) = ");
		view();

		// Check if an element is present using contains()
		boolean elementFound = minHeap.contains(11);
		System.out.println("minHeap.contains(11) = " + elementFound);
		elementFound = minHeap.contains(16);
		System.out.println("minHeap.contains(16) = " + elementFound);
	}
}

Output

Conclusion

Min heaps are widely used to retrieve the smallest element in a pool of elements in constant time. There are plenty of other applications of this data structure, however you can choose any method to implement this. Needless to say, you have to practice with patience to get good at it. So let’s get our muscles moving and get to work!