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

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.
Null Elements: PriorityQueue does not permit null elements.
Duplicates: Allows duplicate elements.
Not Synchronized: The PriorityQueue class itself is not synchronized. For concurrent access, consider using PriorityBlockingQueue.

Common Methods

add(E e) / offer(E e): Inserts the specified element into this priority queue.
```
 minHeap.add(5);
 minHeap.offer(3);
```

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

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

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

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

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

Insertion and Removal: For PriorityQueue, insertion and removal operations are O(log n).
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.

Vineeth Chivukula