Heap Implementation in Java
The root node or parent node of a Java heap is compared to its left and right offspring, and the children are then ordered in line with the comparison.Assuming that x is the root node and y is a child node, the relation key(x)=key(y) will produce a min-heap, and this relation is known as the "Heap Property."
Heap can be categorized into Min heap and Max heap based on the relationship between parent and child nodes. Let's break down each of them individually and implement the Java code.
Min Heap
A whole binary tree on its own is an unique kind of heap data structure called as min heap.The characteristics of the Min heap are as follows:
- The value of the heap's root node is always lower than that of the other nodes.
- The key value of each internal node is always less than or equal to the value of its children.
In the Min heap, we can carry out the following three operations:
- getMin(): It gives back Min Heap's root element. The operation's time complexity is O. (1).
- extractMin(): MinHeap's minimum element is removed. This operation has an O(Log n) time complexity since it is necessary to keep the heap property (by executing heapify()) after deleting the root.
- Insert (): Inserting a new key takes O (Log n) time. We add a fresh key to the tree's tip. If a new key is larger than its parent key, we don't need to do anything. Otherwise, we must ascend to restore the violated heap property.
Example:
// java program to demonstrate heap implementation
class HI {
// Members of this class's variables
private int[] Heap;
private int s;
//ms stands maxsize
private int ms;
// declaring static and unified
private static final int FR = 1;
// Constructor of this class
public HI(int ms)
{
// This keyword refers to current object itself
this.ms = ms;
this.s = 0;
Heap = new int[this.ms + 1];
Heap[0] = Integer.MIN_VALUE;
}
//returning the parent position for the node that is presently at position
private int p(int position) {return position / 2;}
// returning the left child's position for the node that is presently at position
private int lChild(int position) { return (2 * position); }
// returning the right child's location for the node that is presently at position
private int rChild(int pos)
{
return (2 * position) + 1;
}
// if the supplied node is a leaf node, returning true
private booleanisLeaf(int position)
{
if (position> (s / 2)) {
return true;
}
return false;
}
// To switch two heap nodes
private void swap(int fposition, int sposition)
{
int temp;
temp = Heap[fposition];
Heap[fposition] = Heap[sposition];
Heap[sposition] = temp;
}
// To heapify the node at positon
private void minHeapify(int position)
{
if(!isLeaf(position)){
int swapPosition= position;
// exchange with the smallest of the two kids to see if the right kid is there. If not, the default value is "0," and the parent node is substituted.
if(rChild(position)<=s)
swapPos = Heap[lChild(position)]<Heap[rChild(position)]?lChild(position):rChild(position);
else
swapPosition= Heap[lChild(position)];
if(Heap[position]>Heap[lChild(position)] || Heap[position]> Heap[rChild(position)]){
swap(position,swapPosition);
minHeapify(swapPosition);
}
}
}
// To insert a node into the heap
public void insert(int ele)
{
if (s >= m) {
return;
}
Heap[++s] = ele;
int cur = s;
while (Heap[cur] < Heap[parent(cur)]) {
swap(cur, parent(cur));
cur = parent(cur);
}
}
// To print the contents of the heap
public void print()
{
for (int i = 1; i<= s / 2; i++) {
// Printing the parent and both childrens
System.out.print(
" P: " + Heap[i]
+ " L CHILD: " + Heap[2 * i]
+ " R CHILD:" + Heap[2 * i + 1]);
// By here new line is required
System.out.println();
}
}
// To remove and return the minimum element from the heap
public int remove()
{
int pop = Heap[FR];
Heap[FR] = Heap[s--];
minHeapify(FR);
return pop;
}
// driver method
public static void main(String[] arg)
{
// Display message
System.out.println("The Min Heap is ");
// Creating object opf class in main() methodn
HImh = new HI(15);
// Inserting element to minheap using insert() method
// Custom input entries
mh.insert(5);
mh.insert(3);
mh.insert(17);
mh.insert(10);
mh.insert(84);
mh.insert(19);
mh.insert(6);
mh.insert(22);
mh.insert(9);
// Print all elements of the heap
mh.print();
// Removing minimum value from above heapand printing it
System.out.println("The Min val is "
+ mh.remove());
}
}
Output:
The Min Heap is
P: 3 L CHILD: 5 R CHILD :6
P: 5 L CHILD: 9 R CHILD :84
P: 6 L CHILD: 19 R CHILD :17
P: 9 L CHILD: 22 R CHILD :10
The Min val is 3
Java Program to Demonstrate Heap Implementation Using Library Functions
import java.util.*;
// Main class
class LF {
// Main driver method
public static void main(String args[])
{
// Creating empty priority queue
PriorityQueue<Integer>qQueue
= new PriorityQueue<Integer>();
// Adding items to the priority queue using add() method
qQueue.add(100);
qQueue.add(300);
qQueue.add(200);
qQueue.add(4000);
// Printing the most priority element
System.out.println("peek function:"
+ qQueue.peek());
// Printing all elements
System.out.println("The queue elements:");
// Using an Iterator to iterate over objects and making an Iterator class
Iterator ir = qQueue.iterator();
// utilising the next() method to iterate until there is only one element left in the object
while (ir.hasNext())
System.out.println(ir.next());
// Taking out the highest priority component (also known as the head) and printing the revised pQueue using poll ()
qQueue.poll();
System.out.println("After removing an element "
+ "with poll function:");
// Again creating iterator object
Iterator<Integer> ir2 = qQueue.iterator();
while (ir2.hasNext())
System.out.println(ir2.next());
// Removing 300 using remove()
qQueue.remove(300);
System.out.println("after removing 300 with"
+ " remove function:");
// Again creating iterator object
Iterator<Integer> ir3 = qQueue.iterator();
while (ir3.hasNext())
System.out.println(ir3.next());
// Using contains, determine whether an element is present ()
booleanbo = qQueue.contains(200);
System.out.println("Priority queue contains 200 "
+ "or not: " + bo);
// Using toArray() to retrieve objects from the queue and printing the array
Object[] a = qQueue.toArray();
System.out.println("Value in array: ");
for (int i = 0; i<a.length; i++)
System.out.println("Value: "
+ a[i].toString());
}
}
Output:
Peek function: 100
The queue elements:
100
300
200
4000
After removing an element with poll function:
200
300
4000
after removing 300 with remove function:
200
4000
Priority queue contains 200 or not: true
Value in array:
Value: 200
Value: 4000
Max Heap
In Java, the Max heap is an additional unique type of heap data structure that is also a whole binary tree by itself. The following characteristics apply to Max heap:
In comparison to the other nodes of the heap, the value of the root node is always higher.
The key value of each internal node is always greater than or equal to that of its siblings.
We have three operations in max heap:
- insertNode (): By including a new key at the end of the tree, we may conduct insertion into the Max heap. We must traverse the key upwards to satisfy the heap property if the value of the inserted key is bigger than the value of its parent node. The time it takes to insert data is O(log n).
- ExtractMax (): The removal of the maximum value node, or the heap's root node, is one of the most crucial actions that we carry out. We must ensure that the heap property is preserved after removing the root node. The maximum element is removed from the heap in O(Log n) time using the extractMax() procedure.
- getMax (): The root node of the heap, or the maximum element in O(1) time, is obtained using the getMax() procedure.
Java Program to Demonstrate Max Heap Implementation
public class MH {
private int[] Heap;
private int s;
private int ms;
// Initializes a max heap with the specified maximum capacity.
public MH(int ms)
{
// This keyword refers to current instance itself
this.ms = ms;
this.s = 0;
Heap = new int[this.ms];
}
// Returning position of parent
private int parent(int position) {return (position - 1) / 2; }
// Returning l children
private int lChild(int position) { return (2 * position) + 1; }
// Returning r children
private int rChild(int position)
{
return (2 * position) + 2;
}
// Returning true of given node is leaf
private booleanisLeaf(int position)
{
if (position> (s / 2) && position<= s) {
return true;
}
return false;
}
// Swapping nodes
private void swap(int fpositon, int sposition)
{
int temp;
temp = Heap[fposition];
Heap[fposition] = Heap[sposition];
Heap[sposition] = temp;
}
// Function to max heapify a given subtree in recursive mode
private void maxHeapify(int position)
{
if (isLeaf(position))
return;
if (Heap[position] < Heap[lChild(position)]
|| Heap[position] < Heap[rChild(position)]) {
if (Heap[lChild(position)]
> Heap[rChild(position)]) {
Swap(position, lChild(position));
maxHeapify(lChild(positon));
}
else {
swap(position, rChild(position));
maxHeapify(rChild(position));
}
}
}
// Inserts a new element to max heap
public void insert(int ele)
{
Heap[s] = ele;
// Traverse up and fix violated property
int cur = s;
while (Heap[cur] > Heap[parent(cur)]) {
swap(cur, parent(cur));
cur = parent(cur);
}
s++;
}
// To display heap
public void print()
{
for (int i = 0; i< s / 2; i++) {
System.out.print("P Node : " + Heap[i]);
if (lChild(i)
< s) // if the kid is outside of the array's bounds
System.out.print(" LChild Node: "
+ Heap[lChild(i)]);
if (rChild(i)
< s) // If the right child index cannot be outside of the array's index,
System.out.print(" R Child Node: "
+ Heap[rChild(i)]);
System.out.println(); // for new line
}
}
// Remove an element from max heap
public int extractMax()
{
int p = Heap[0];
Heap[0] = Heap[--size];
maxHeapify(0);
return p;
}
public static void main(String[] arg)
{
// Display message for better readability
System.out.println("The Max Heap is ");
MaxHeapmh = new MaxHeap(15);
// Inserting nodes Custom inputs
mh.insert(50);
mh.insert(30);
mh.insert(170);
mh.insert(100);
mh.insert(840);
mh.insert(190);
mh.insert(60);
mh.insert(220);
mh.insert(90);
// Calling mh() as defined above
mh.print();
// Print and display the maximum value in heap
System.out.println("The max val is "
+ mh.extractMax());
}
}
Output:
The Max Heap is
P Node: 840 L Child Node: 220 R Child Node: 190
P Node: 220 L Child Node: 170 R Child Node: 100
P Node: 190 L Child Node: 50 R Child Node: 60
P Node: 170 L Child Node: 30 R Child Node: 90
The max val is 840
Java Program to Demonstrate Max Heap Implementation Using Library Functions
import java.util.*;
// Main class
class HM {
// Main driver method
public static void main(String args[])
{
// Creating empty priority queue
PriorityQueue<Integer>qQueue
= new PriorityQueue<Integer>(
Collections.reverseOrder());
// Adding items to our priority queueusing add() method
qQueue.add(100);
qQueue.add(300);
qQueue.add(200);
qQueue.add(4000);
// Printing the most priority element
System.out.println("peek function:"
+ qQueue.peek());
// Printing all elements
System.out.println("The queue elements:");
Iterator ir = qQueue.iterator();
while (ir.hasNext())
System.out.println(ir.next());
// Taking out the highest priority component (also known as the head) and printing the revised pQueue using poll ()
qQueue.poll();
System.out.println("After removing an element "
+ "with poll function:");
Iterator<Integer> ir2 = qQueue.iterator();
while (ir2.hasNext())
System.out.println(ir2.next());
// Removing 30 using remove() method
qQueue.remove(300);
System.out.println("after removing 300 with"
+ " remove function:");
Iterator<Integer> ir3 = qQueue.iterator();
while (ir3.hasNext())
System.out.println(ir3.next());
// Check if an element is present using contains()
booleanbo = qQueue.contains(200);
System.out.println("Priority queue contains 200 "
+ "or not: " + bo);
// Using toArray() to retrieve objects from the queue and printing the array
Object[] a = qQueue.toArray();
System.out.println("Value in array: ");
for (int i = 0; i<a.length; i++)
System.out.println("Value: "
+ a[i].toString());
}
}
Output:
Peek function: 400
The queue elements:
4000
300
200
100
After removing an element with poll function:
300
100
200
after removing 30 with remove function:
200
100
Priority queue contains 20 or not: true
Value in array:
Value: 200
Value: 10
Application of Heap Data Structure
- A priority queue is built using a heap.
- One of the quickest sorting algorithms is heap sort, which has a time complexity of O(N*log(N) and is simple to use.
- Unlike the queue in breadth-first search, the Best First Search (BFS) technique is implemented using a priority queue. BFS is an informed search.
Advantages of Heap Data Structure
- Less complicated in terms of time; O is all that is required to add or remove an element from a heap (log N).
- The smallest and largest numbers can be found to aid in arithmetic.
- The temporal complexity is constant O, simply to have a quick look at the previous element (1).
- Arrays may be used to do this; pointer space is not need to be added.
- An easy-to-implement binary heap is a balanced binary tree.
- It takes O(N) time to generate a heap.
Disadvantages of Heap Data Structure
- Searching an element in a heap has an O time complexity (N).
- The heap requires O(N) time while BST merely requires O(log N) time to determine a successor or predecessor of an element.
- While BST only requires O(N) time, it would take O(N*log N) to display the entire heap in sorted order.
- Since heap memory is used everywhere, memory management is more difficult. The old generations and the new generations, etc., of heap memory are separated during Java garbage collection.