Understanding Java Heaps for DSA

In Java, heaps are typically implemented using the PriorityQueue class, which is part of the java.util package. A heap is a specialized tree-based data structure that satisfies the heap property. The PriorityQueue class provides an implementation of a priority queue, which can be used as a min-heap or max-heap, depending on the comparator provided.

Key Characteristics

1. Heap Property: Heaps are typically implemented as complete binary trees. The parent node always has a smaller value than its children for a min-heap. The parent node always has a larger value than its children for a max-heap.

2. Null Elements: PriorityQueue does not permit null elements.

3. Duplicates: Allows duplicate elements.

4. Not Synchronized: The PriorityQueue class itself is not synchronized. For concurrent access, consider using PriorityBlockingQueue.

Common Methods

1. add(E e) / offer(E e): Inserts the specified element into this priority queue.

    minHeap.add(5);
    minHeap.offer(3);
   

2. remove() / poll(): Retrieves and removes the head of this queue.

    int minElement = minHeap.remove(); // throws NoSuchElementException if empty
    int minElement = minHeap.poll(); // returns null if empty
   

3. element() / peek(): Retrieves, but does not remove, the head of this queue.

    int headElement = minHeap.element(); // throws NoSuchElementException if empty
    int headElement = minHeap.peek(); // returns null if empty
   

Implementations

1. PriorityQueue: An unbounded priority queue based on a priority heap.

    PriorityQueue<Integer> minHeap = new PriorityQueue<>();
    PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Comparator.reverseOrder());
   

2. PriorityBlockingQueue: A blocking variant of PriorityQueue that provides thread safety.

    PriorityBlockingQueue<Integer> blockingMinHeap = new PriorityBlockingQueue<>();
    PriorityBlockingQueue<Integer> blockingMaxHeap = new PriorityBlockingQueue<>(11, Comparator.reverseOrder());
   

Iteration

Heaps, like PriorityQueue, can be iterated using various methods such as for-each loop, iterators and streams. However, the iteration order is not guaranteed to be in heap order.

for (int num : nums) {
    System.out.println(item);
}

Iterator<Integer> iterator = minHeap.iterator();
while (iterator.hasNext()) {
    System.out.println(iterator.next());
}

minHeap.forEach(System.out::println);

Performance Considerations

1. Insertion and Removal: For PriorityQueue, insertion and removal operations are O(log n).

2. Accessing the Minimum/Maximum Element: The minimum or maximum element (depending on the heap type) is O(1).

Thank you for reading!

You can support me by buying me a book.