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

Java Implements Keyword

To understand about the keyword implements we need to learn about the concept of the interfaces and inheritance in java programming languages. So let us learn about the interface and...

3 minutes read.

Java Short Keyword

Java supports eight different primitive datatypes. The language has predefined primitive datatypes that are given keyword names. Let's take a closer look at each of the eight primitive data types....

3 minutes read.

Access Modifier in Java

The access modifiers in java are used to change the accessibility and scope of a method, constructor, class, and fields. If you are aware of C++ language, when we declare any member...

2 minutes read.

Java 9 Interface Private Method

Java 9 provides us the facility to include private methods inside the java interface. In java 8 and earlier versions, we are supposed to use only constant variables and abstract...

3 minutes read.

XNOR operator in Java

The opposite of the binary equivalent of XOR is given by XNOR. Truth table: XYXNOR001010100111 If the bits are the same, it returns 1, else it returns 0. Examples:  Input: 10 20 Output : 1 A Binary...

3 minutes read.

Java Code Optimization

We encounter the idea of optimization while working on any Java application. It is essential that the code we write is not only clear and error-free but also optimized, meaning...

9 minutes read.

JDBC Program in Java

JDBC Program in Java JDBC is an API that defines how a client may access a database. It is a part of Java Standard Edition (Java SE). JDBC stands for Java...

4 minutes read.

Java Read File

Java provides its users with many ways of reading a file. To read a text file, you can use a FileReader, BufferedReader, or Scanner. Each utility offers something special for...

6 minutes read.

Java Editors

A straightforward text editor may be used to create Java applications. However, a Java integrated programming environment (IDE) enables the software developer to create programs more quickly. An IDE offers...

4 minutes read.

Blockchain in Java

Blockchain is a continuously expanding ledger that maintains an immutable, secure, and chronological record of all transactions that have ever occurred. It can be utilized to securely transfer money, assets,...

9 minutes read.

Java Math negateExact() Method

The negateExact() method of Math class returns the negation for the specified argument, throwing an exception if the result overflows an int or a long. Syntax: public static int negateExact (int a)public...

1 minute read.

How to avoid deadlock in java

Deadlock: A deadlock is an event that never going to occur. In java, deadlock is just a part of the multithreading. It is an environment that allows us to run multiple...

4 minutes read.

Access modifiers in Java

Access modifiers in Java with Example In Java, there are two types of access modifiers one is a non-access modifier, and other is access modifier. If we talk about access modifier, there...

3 minutes read.

Nth Term of Geometric Progression in Java

There are 3 numbers provided. The geometric progression's initial term is the first number. The second number is the geometric progression's common ratio, and the third number represents the nth...

3 minutes read.

Java Program to Create Set of Pairs Using HashSet

HashSet in Java: HashSet is an assortment in Java that has a place with java.util bundle. It inside utilises HashMap to store components. It is an execution of the Set connection...

11 minutes read.

Pernicious Number in Java

If the number of 1s in a number appearing in the binary representation is the prime number, such a number is known as a pernicious number. A pernicious number always corresponds to...

4 minutes read.

Java Set Interface

We use set when we don't want to allow duplicate entries. All Set implementations do not allow duplicates. HashSet: This class stores its elements in hash tables. It uses the hashCode()...

3 minutes read.

How to make Java Projects

Ant and Maven are both offered by NetBeans for the development of Java applications. When using Ant, the IDE creates an Ant build script depending on the settings you select...

6 minutes read.

Generics in Java

Generics in Java Parameterizedtypes mean generic. Generics allow types (Character, Integer, String, …, etc., as well as user-defined types) to act as parameters to interfaces, classes, and methods. Generics in Java...

9 minutes read.

Java Wrapper classes

Java Wrapper classes A wrapper class is a class whose object contains a primitive data type; moreover it provides a way to use primitive data type (int, boolean, etc.) as objects. Wrapper...

2 minutes read.