Before we get started, it is assumed that you know about a Binary Tree 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 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.

*(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

## 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”.- 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.

## 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
The Min Heap is : [3, 13, 7, 16, 21, 12, 9]
Parent : 3 Left : 13 Right :7
Parent : 13 Left : 16 Right :21
Parent : 7 Left : 12 Right :9
The Min Value is : 3
The Min Heap is : [7, 13, 9, 16, 21, 12, 9] // after removing the root
Parent : 7 Left : 13 Right :9
Parent : 13 Left : 16 Right :21
Parent : 9 Left : 12

## 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
minHeap.add(3) = 3
minHeap.view() = 3 13 7 16 21 12 9
minHeap.peek() = 3
minHeap.poll() = 7 13 9 16 21 12
minHeap.remove(7) = 9 13 12 16 21
minHeap.contains(11) = false
minHeap.contains(16) = true

GO TO FULL VERSION

Implementation of Min Heap in Java - Using Arraysexplanation was helpful. Thank you 😊 Have Implemented myself after understanding from hereThat's not true for aBinary 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)Binary Tree, that property is true for aBinary Search Tree