Heap and Priority Queue in Java Cheat Sheet

8779

Heap and Priority Queue in Java Cheat Sheet

In Java, the PriorityQueue and Heap (which is commonly implemented via PriorityQueue) are used to handle priority-based elements. A heap is a specialized binary tree-based data structure that satisfies the heap property. The most common types of heaps are Min-Heap and Max-Heap.

1. PriorityQueue in Java

PriorityQueue is a part of the java.util package and is a queue that orders elements based on their priority.
The default implementation of PriorityQueue uses a Min-Heap (smallest element at the top).
Max-Heap can be implemented by providing a custom comparator.

Basic Syntax for `PriorityQueue`:

import java.util.PriorityQueue;

PriorityQueue<Type> pq = new PriorityQueue<Type>();   // Min-Heap (default)
PriorityQueue<Type> pqMax = new PriorityQueue<>(Comparator.reverseOrder()); // Max-Heap

2. Common Operations on `PriorityQueue`:

Operation	Description	Time Complexity
add(e)	Inserts element `e` into the queue.	O(log n)
offer(e)	Inserts element `e` into the queue.	O(log n)
poll()	Removes and returns the top element.	O(log n)
peek()	Returns the top element without removing it.	O(1)
remove()	Removes a specified element from the queue.	O(n)
size()	Returns the number of elements in the queue.	O(1)
clear()	Removes all elements from the queue.	O(n)
contains(e)	Checks if the queue contains the element `e`.	O(n)

Example: Min-Heap PriorityQueue (Default):

import java.util.PriorityQueue;

public class Main {
    public static void main(String[] args) {
        // Create a Min-Heap priority queue
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        
        pq.add(10);
        pq.add(5);
        pq.add(20);
        pq.add(15);

        System.out.println("Top element (min): " + pq.peek()); // 5
        
        // Polling (removing the top element)
        System.out.println("Removed element: " + pq.poll()); // 5
        System.out.println("Top element (after poll): " + pq.peek()); // 10
    }
}

Example: Max-Heap PriorityQueue (Custom Comparator):

import java.util.PriorityQueue;
import java.util.Comparator;

public class Main {
    public static void main(String[] args) {
        // Create a Max-Heap priority queue
        PriorityQueue<Integer> pqMax = new PriorityQueue<>(Comparator.reverseOrder());

        pqMax.add(10);
        pqMax.add(5);
        pqMax.add(20);
        pqMax.add(15);

        System.out.println("Top element (max): " + pqMax.peek()); // 20
        
        // Polling (removing the top element)
        System.out.println("Removed element: " + pqMax.poll()); // 20
        System.out.println("Top element (after poll): " + pqMax.peek()); // 15
    }
}

3. Heap Operations using `PriorityQueue`

Java’s PriorityQueue is based on a binary heap. The heap can be a Min-Heap (default) or a Max-Heap (custom comparator).

Heap Property:

Min-Heap: Parent node is smaller than its children.
Max-Heap: Parent node is larger than its children.

4. Using PriorityQueue for Heap Sort:

To sort elements using Heap Sort, we can utilize the PriorityQueue. Here’s an example of Heap Sort using the Min-Heap (default PriorityQueue):

import java.util.PriorityQueue;

public class HeapSortExample {
    public static void main(String[] args) {
        int[] nums = {10, 5, 20, 15, 30, 25};
        
        // Min-Heap PriorityQueue
        PriorityQueue<Integer> pq = new PriorityQueue<>();

        // Add all elements to the priority queue (Min-Heap)
        for (int num : nums) {
            pq.add(num);
        }

        // Extract elements in sorted order
        while (!pq.isEmpty()) {
            System.out.print(pq.poll() + " ");  // 5 10 15 20 25 30
        }
    }
}

5. PriorityQueue with Objects

You can use custom objects in a PriorityQueue by implementing the Comparable interface or providing a custom Comparator.

Example: Custom Object with Comparable:

import java.util.PriorityQueue;

class Person implements Comparable<Person> {
    String name;
    int age;

    public Person(String name, int age) {
        this.name = name;
        this.age = age;
    }

    @Override
    public int compareTo(Person other) {
        return Integer.compare(this.age, other.age);  // Min-Heap based on age
    }

    @Override
    public String toString() {
        return name + " (" + age + ")";
    }
}

public class Main {
    public static void main(String[] args) {
        PriorityQueue<Person> pq = new PriorityQueue<>();

        pq.add(new Person("Alice", 30));
        pq.add(new Person("Bob", 25));
        pq.add(new Person("Charlie", 35));

        while (!pq.isEmpty()) {
            System.out.println(pq.poll());  // Bob (25), Alice (30), Charlie (35)
        }
    }
}

Example: Custom Object with Comparator:

import java.util.PriorityQueue;
import java.util.Comparator;

class Person {
    String name;
    int age;

    public Person(String name, int age) {
        this.name = name;
        this.age = age;
    }

    @Override
    public String toString() {
        return name + " (" + age + ")";
    }
}

public class Main {
    public static void main(String[] args) {
        // Custom comparator for Max-Heap based on age
        PriorityQueue<Person> pq = new PriorityQueue<>(Comparator.comparingInt(p -> -p.age));

        pq.add(new Person("Alice", 30));
        pq.add(new Person("Bob", 25));
        pq.add(new Person("Charlie", 35));

        while (!pq.isEmpty()) {
            System.out.println(pq.poll());  // Charlie (35), Alice (30), Bob (25)
        }
    }
}

6. Common Use Cases for Priority Queue / Heap:

Heap Sort: Sorting using Min-Heap or Max-Heap.
Dijkstra's Algorithm: Finding the shortest path in a graph.
Huffman Encoding: Data compression algorithm.
Median of a Data Stream: Using two heaps to find the median.
Kth Largest/Smallest Element in an Array: Using a Min-Heap or Max-Heap.
Merge k Sorted Lists: Merging multiple sorted lists using a Min-Heap.

7. Additional Tips:

The PriorityQueue class is not thread-safe. If you need a thread-safe version, consider using PriorityBlockingQueue from java.util.concurrent.
PriorityQueue is not fixed in size; it grows dynamically as needed.
Heap operations (add, remove) take (O(\log n)), but peek operation takes constant time (O(1)).

This cheat sheet covers the basics of PriorityQueue and heap operations in Java. It helps with understanding how to implement heap-based data structures, solve problems like sorting, and manage priority-based data efficiently.

Comments (4)