Implement MinMax Heap in Java
 Introduction to MinMax Heap in Java

Implement MaxHeap With the
PriorityQueue
Class andCollections.reverseOrder()
in Java 
Implement MinHeap With the
PriorityQueue
Class in Java
This article will implement a maxheap and a minheap using the PriorityQueue
class. We will also demonstrate the insertion and deletion of the elements from the heap.
Introduction to MinMax Heap in Java
A heap is a data structure based upon trees, and it forms a complete binary tree. Heaps are represented as an array. There are two types of heaps, and they are minimum heap and maximum heap. The minimum heap, also known as the minheap, has the smallest value in its root node or the parent node. Similarly, the maxheap has the largest value in the root node or the parent node. Therefore, the heap data structure makes it easier to extract the largest and the smallest element from an array. We can get the largest and the smallest element in O(1)
. The complexity to remove or insert the elements to and from the heap is O(log N)
.
A minmax heap is a data structure that contains alternating minimum and maximum levels. The root node contains the smallest value, and the next level below it represents the largest value. The minimum values are represented with even levels like 0, 2, 4. The odd levels like 1, 3, 5 represent the maximum values.
Implement MaxHeap With the PriorityQueue
Class and Collections.reverseOrder()
in Java
We can use the PriorityQueue
class to implement the heaps in Java. The class implements the minheap by default, and we can use the reverseOrder()
method from Collections to implement the maxheap. We can use the peek()
method to display the element from the root node in a heap. The poll()
method returns and removes the value at the root node. We can use the contains()
method to check if an element exists in a heap.
For example, import everything from the java.util
package. Create a class MaxHeap
and write the main method. Then create an instance of the PriorityQueue
class as pq
. Use the generic type to create the Integer
instance. Write Collections.reverseOrder()
in the parenthesis while creating the object. Use the add()
method to add four integer values. Call the peek()
method with the object pq
and print it. Then, use the poll()
method on the object. Next, call the remove()
method with a value 30
as the parameter and then print the elements in the array using the iterator()
and hasNext()
methods. Finally, use the contains()
method with a parameter 20
.
In the example below, the import java.util.*
will import the PriorityQueue
class, which we used to create a maxheap. We added the values 1
, 2
, 3
, and 4
to the heap. The peek()
method returned the value 4
, which is the largest in a heap. Then, the poll()
method removed the maximum number, 4
. Then, we used the remove()
method to remove the number 3
, and we printed the remaining elements in a heap. It printed the values 1
and 2
as we already removed 3
and 4
. Finally, we checked if the heap contains a number 2
using the contains()
method. It returned true
as there exists the number in a heap. Thus, we implemented the maxheap using the PriorityQueue
class with the use of Collectios.reverseOrder()
.
Example 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
Implement MinHeap With the PriorityQueue
Class in Java
The PriorityQueue
class implments min heap by default. We apply the same method of implementation for the minheap as we did for the maxheap. We use the same methods like peek()
, remove()
, poll()
and contains()
to perform the same operations.
In the example below, we added the numbers 1
, 2
, 3
, and 4
in a heap. The peek()
method returned the element in the root node, which is 1
as shown in the output. We used poll()
method to remove the root node element 1
. We again removed the value 3
from the heap with the remove()
function. After removing these values, our heap only contains the elements 2
and 4
. Finally, we used the contains()
method to check if we value 3
in a heap. As we already removed it, the method returns a false
value. Thus, we implemented a minheap using the PriorityQueue
class.
Example 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