JIYIK CN >

In this article, we will implement a max heap and a min heap using PriorityQueuethe class. We will also demonstrate inserting and removing elements from the heap.

Introduction to Min-Max Heap in Java

Heap is a tree-based data structure, which forms a complete binary tree. Heap is represented as an array. There are two types of heaps, they are min heap and max heap. Min heap, also known as minimum heap, has the minimum value in its root node or parent node. Similarly, max heap has the maximum value in the root node or parent node. Therefore, heap data structure makes it easier to extract the maximum and minimum elements from the array. We can get O(1)the largest and smallest element in . The complexity of deleting or inserting an element from a heap is O(log N).

A min-max heap is a data structure that contains alternating minimum and maximum levels. The root node contains the minimum value and the next level represents the maximum value. The minimum value is represented by an even-numbered level (such as 0, 2, 4). The odd-numbered levels (such as 1, 3, 5) represent the maximum value.

Implementing a max heap in Java using PriorityQueuethe class andCollections.reverseOrder()

We can PriorityQueueimplement a heap in Java using the class. This class implements a min heap by default, and we can use reverseOrder()the method in Collections to implement a max heap. We can use peek()the method to display the element of the root node in the heap. poll()The method returns and removes the value of the root node. We can use contains()the method to check if an element exists in the heap.

For example, java.utilimport everything from the package. Create a class MaxHeapand write the main method. Then create an PriorityQueueinstance of the class as pq. Create an instance of using generic types Integer. Write in brackets while creating an object Collections.reverseOrder(). Use add()the method to add four integer values. pqCall peek()the method with the object and print it. Then, use the method on the object poll(). Next, call the method with the value 30as a parameter remove()and then use the iterator()and hasNext()methods to print the elements in the array. Finally, use the method 20with the parameter .contains()

In the following example, the class import java.util.*is imported, which we use to create a max heap PriorityQueue. We add the values 1​​, 2, 3and 4to the heap. peek()The method returns value 4, which is the largest value in the heap. Then, poll()the method removes the largest number 4. We then use remove()the method to remove the number 3and print the remaining elements in the heap. It prints the values 1​​and 2because we have removed 3and 4. Finally, we use contains()the method to check if the heap contains a number 2. It returns truebecause the number exists in the heap. Thus, we have implemented a max heap using PriorityQueuethe classes and .Collectios.reverseOrder()

Sample code:

import java.util.*;

class MaxHeap {
  public static void main(String args[]) {
    PriorityQueue<Integer> pq = new PriorityQueue<Integer>(Collections.reverseOrder());
    pq.add(1);
    pq.add(3);
    pq.add(2);
    pq.add(4);
    System.out.println("The highest value in the heap:" + pq.peek());
    pq.poll();
    pq.remove(3);
    System.out.println("after removing 3:");
    Iterator<Integer> itr = pq.iterator();
    while (itr3.hasNext()) System.out.println(itr.next());
    boolean b = pq.contains(2);
    System.out.println("Does the heap contains 2 ?" + b);
  }
}

Output:

The highest value in the heap:4
after removing 3:
2
1
Does the heap contains 2 ?true

PriorityQueueImplementing a min heap in Java using the class

PriorityQueueThe class implements a min heap by default. We apply the same implementation approach to the min heap as we did to the max heap. We use the same methods as peek(), , remove(), poll()and , contains()etc. to perform the same operations.

In the following example, we added the numbers 1, 2, 3and to the heap 4. peek()The method returns the element in the root node, i.e. 1, , as shown in the output. We poll()removed the root node element using the method 1. We again remove()removed the value from the heap using the function 3. After removing these values, our heap contains only the elements 2and 4. Finally, we contains()check if the value is in the heap using the method 3. Since we have removed it, the method returns a falsevalue of . Thus, we PriorityQueuehave implemented a min heap using the class.

Sample code:

import java.util.*;

class MinHeap {
  public static void main(String args[]) {
    PriorityQueue<Integer> pq = new PriorityQueue<Integer>();
    pq.add(1);
    pq.add(3);
    pq.add(2);
    pq.add(4);
    System.out.println("The highest value in the heap:" + pq.peek());
    pq.poll();
    pq.remove(3);
    System.out.println("after removing 3:");
    Iterator<Integer> itr = pq.iterator();
    while (itr.hasNext()) System.out.println(itr.next());
    boolean b = pq.contains(3);
    System.out.println("Does the heap contains 3 ?" + b);
  }
}

Output:

The highest value in the heap:1
after removing 3:
2
4
Does the heap contains 2 ?false