How to create min heap and max heap in Java using PriorityQueue

A heap is a specific tree structure that follows the heap property. This property states that each node’s value is either smaller than or equal to (or greater than or equal to) its children’s values. Heaps are fundamental data structures that are crucial in various algorithms and applications. In Java, the PriorityQueue class provides a convenient way to implement min heap and max heap structures.

The Java PriorityQueue class

Java’s java.util package includes the PriorityQueue class, implementing a priority queue via a binary heap. Elements within this priority queue are ordered based on their natural ordering or a provided comparator.

Creating a min heap

In a min heap, the smallest element is positioned at the top (root), and for any given node i, its value is less than or equal to the values of its children.

canvasAnimation-image

Creating a min heap in Java using PriorityQueue is quite straightforward. PriorityQueue’s default behavior is to create a min heap, where the smallest element has the highest priority.

import java.util.PriorityQueue;
class MinHeapExample {
    public static void main(String[] args) {
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        // Adding elements to the min heap
        minHeap.add(5);
        minHeap.add(2);
        minHeap.add(8);
        minHeap.add(1);
        // Polling elements from the min heap
        while (!minHeap.isEmpty()) {
            System.out.println(minHeap.poll());
        }
    }
}
Implementing a min heap in Java

In the code example above, the minHeap PriorityQueue is populated with elements, and the poll()This method removes and returns the top element from the priority queue. method efficiently retrieves and removes elements in an ascending order.

Creating a max heap

A max heap is a heap where the largest element is at the root, and for any given node i, its value is greater than or equal to the values of its children.

canvasAnimation-image

Creating a max heap in Java using the PriorityQueue class can use a custom comparator to reverse the ordering.

In the MaxHeapExample class, the PriorityQueue is created with a custom comparator using Collections.reverseOrder(), which reverses the natural ordering of elements, effectively creating a max heap. 

import java.util.PriorityQueue;
import java.util.Collections;
class MaxHeapExample {
    public static void main(String[] args) {
        // Creating a max heap using a custom comparator
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
        // Adding elements to the max heap
        maxHeap.add(5);
        maxHeap.add(2);
        maxHeap.add(8);
        maxHeap.add(1);
        // Polling elements from the max heap
        while (!maxHeap.isEmpty()) {
            System.out.println(maxHeap.poll());
        }
    }
}
Implementing a max heap in Java

In the code example above, the maxHeap PriorityQueue utilizes a custom comparator, effectively creating a max heap. Elements are added and subsequently retrieved in a descending order using the poll() method.

Conclusion

Using PriorityQueue to implement max and min heaps offers a straightforward and efficient solution for managing priority-based data structures. The PriorityQueue class provides built-in functionality for heap operations like insertion, removal, and retrieval of elements with minimal code complexity. This approach offers a flexible and convenient way to handle priority queue requirements in various algorithmic tasks and data processing scenarios in Java programming. By default, PriorityQueue in Java implements a min heap, but a custom comparator can be provided to modify its behavior to that of a max heap. Understanding these implementations is crucial for efficiently solving problems related to priority queues and heaps in Java programming.

Free Resources

Copyright ©2025 Educative, Inc. All rights reserved