How to Implement Min-Max Heap in Java

1. Introduction to Min-Max Heap in Java
2. Implement Max-Heap With the PriorityQueue Class and Collections.reverseOrder() in Java
3. Implement Min-Heap With the PriorityQueue Class in Java

This article will implement a max-heap and a min-heap using the PriorityQueue class. We will also demonstrate the insertion and deletion of the elements from the heap.

Introduction to Min-Max 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 min-heap, has the smallest value in its root node or the parent node. Similarly, the max-heap 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 min-max 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 Max-Heap 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 min-heap by default, and we can use the reverseOrder() method from Collections to implement the max-heap. 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 max-heap. 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 max-heap 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 Min-Heap With the PriorityQueue Class in Java

The PriorityQueue class implments min heap by default. We apply the same method of implementation for the min-heap as we did for the max-heap. 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 min-heap 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