Logo
×

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.

Related Topics

How to add 4 Years to the Current Date in Java?

In this tutorial, we will learn how to add 4 years to the local or current date in Java language. We will begin our topic with basic concepts and would...

2 minutes read.

Types of Events in Java

One of Java's key ideas is the principle of an event. Events in Java are activities that result in a change in the state or behavior of an object. The...

4 minutes read.

Java Integer hashCode() method

The hashCode()  method of Java Integer class returns a hash code for this Integer.  Syntax public int hashCode() public static int hashCode(int value)  Parameters The parameter ‘value’ represents a value whose hash code...

1 minute read.

How to check the Java version in cmd

To make programs that can run on our systems, we need to install programming language-related software in our systems. Different programming languages require different types of software, aka IDEs (Integrated...

5 minutes read.

How to run Java Program in Command Prompt

How to run Java Program in Command Prompt In this section, we will learn how to write, save, compile, and execute or run a Java program in the Command Prompt. Note: One...

3 minutes read.

Practical Number in Java

In this tutorial, we will understand what is meant by practical numbers. We will understand it throughthe aid of examples and implementation in a java programming language. The practical numbers...

5 minutes read.

How to open the Java control panel

The many methods for launching the Java control panel will be covered in this section. We will also go through how the Java Control Panel can be used. Java Control Panel The...

2 minutes read.

Fibodiv Number in Java

Before understanding the concept of the fibodiv number, one should realize what the Fibonacci number is. What are Fibonacci Numbers? The Fibonacci sequence of whole numbers is composed of the numbers 0,...

5 minutes read.

Types of Garbage Collector in Java

Garbage collection is a Java feature that offers automatic memory management. The JVM is in charge of it. The programmer does not have to handle object creation and deallocation. We...

3 minutes read.

How to Create a Package in Java?

For the most part, how to create a package in Java generally, a package is defined as a collection of relevant or irrelevant items together in a very major way....

7 minutes read.

How to declare string array in Java

Introduction Array is a data structure with a fixed size, which allows us to store elements of similar type. Data of primitive types like int, char, float, string, etc. can be...

2 minutes read.

Deadlock in Java

Deadlock is when two or more processes wait for the state to do their tasks, but none of them can do so. It is a very common problem that one...

6 minutes read.

Java Math log10() Method

The log10() method of Math class returns the base 10 logarithmic value for the specified double argument. Syntax: public static double log10(double a) Parameters: The parameter ‘a’ represents a double value. Return Value: The log10() method...

2 minutes read.

Difference between this and super in Java

In this article, you will be very well equipped with the knowledge of this keyword and super keyword in java. You will be able to understand where to implement this...

3 minutes read.

Java String copyValueOf() method

copyValueOf() method returns a String that holds the character sequence of the character array. Syntax: copyValueOf(char[] data) Parameters: data : the character array i.e. String Returns: It returns a String that contains the characters of the...

2 minutes read.

How to Convert String to Date in Java

How to Convert String to Date in java You can convert String to Date in Java by using the parse() method. There are two classes which have parse() method namely, DateFormat and SimpleDateFormat classes....

2 minutes read.

Java Pass-by-Reference

In Java, passing parameters can be done using one of two fundamental methods. Pass-by-value is used for the first and pass-by-reference is used for the second. One thing to keep...

2 minutes read.

Java Math IEEEremainder() Method

The IEEEremainder() method of Math class calculates the remainder as prescribed by the IEEE754 standard. This method simply returns the remainder when f1 (dividend) is divided by f2 (divisor). Syntax: public static...

2 minutes read.

Skyline Problem in Java

The skyline of a city is the outer edge of the pattern created by all of its structures when viewed from a distance. Return the skyline that these buildings together...

4 minutes read.

Bad Operand types for Binary Operator Java

We will discuss how to handle issues in bad operand types for binary operator &, bad operand types for binary operator &&, bad operand types for binary operator ==, and...

4 minutes read.