Java Notes
HubArray IntroductionArray OperationsArray Programs — FundamentalsArray Interview QuestionsJagged Array in JavaMulti Dimensional ArrayOne Dimensional Arraybreak and continue in JavaDo-While Loop in JavaFor Loop in JavaIf-Else Statements in JavaNested Loops in JavaSwitch-Case in JavaWhile Loop in JavaJava Compilation ProcessFeatures of JavaYour First Java ProgramHistory of JavaJava EditionsJava Program StructureJDK, JRE, and JVMWhat is Java?Immutable Strings in JavaString Class in JavaString Interview QuestionsString MethodsString Programs — FundamentalsStringBuffer in JavaStringBuilder in JavaComments in JavaData Types in JavaIdentifiers in JavaInput and Output in JavaKeywords in JavaOperators in JavaType Casting in JavaVariables in JavaAbstract Class in JavaAbstraction in JavaAnonymous Class in JavaClass and Object in JavaConstructor in JavaEncapsulation in JavaInheritance in JavaInner Class in JavaInterface in JavaMethod Overloading in JavaMethod Overriding in JavaObject Class in JavaObject Cloning in JavaOOPs IntroductionPolymorphism in Javastatic Keyword in Javasuper Keyword in Javathis Keyword in JavaWrapper Class in JavaCollections Framework OverviewCollections Practice ProgramsComparable vs Comparator in JavaGenerics in JavaIterator in JavaArrayList in JavaLinkedList in JavaStack in Java — Collections FrameworkVector in JavaHashMap in JavaHashtable in JavaLinkedHashMap in JavaTreeMap in JavaArrayDeque in JavaDeque Interface in JavaPriorityQueue in JavaHashSet in JavaLinkedHashSet in JavaTreeSet in JavaException Handling Best PracticesCustom Exceptions in JavaException Hierarchy in JavaFinally Block in JavaException Handling Introductionthrow and throws Keywords in JavaTry-Catch Block in JavaBuffered Streams in JavaByte Streams in JavaCharacter Streams in JavaDeserialization in JavaFile Class in JavaJava NIO PackageSerialization in JavaDate and Time API in Java 8Default and Static Methods in InterfacesFunctional Interface in Java 8Lambda Expression in Java 8Method Reference in Java 8Optional Class in Java 8Stream API in Java 8Creating Threads in JavaDaemon Threads in JavaExecutor Framework in JavaInter-Thread Communication in JavaMultithreading Programs in JavaRunnable Interface in JavaSynchronization in JavaThread Class in JavaThread IntroductionThread Life Cycle in JavaThread Priority in JavaBatch Processing in JDBCCallableStatement in JDBCJDBC ArchitectureJDBC IntroductionJDBC ProjectsMySQL Connection with JDBCPreparedStatement in JDBCResultSet in JDBCStatement Interface in JDBCTransaction Management in JDBCCookies in ServletsExpression Language (EL)GenericServletHttpServletJSP IntroductionJSP Tags and JSTLMVC ArchitectureRequest and Response ObjectsServlet IntroductionServlet Life CycleSession TrackingDependency InjectionAPI GatewayConfig ServerDocker DeploymentEureka Server - Service DiscoverySpring BeansCRUD ApplicationException Handling in Spring BootJWT Authentication — Java ProgrammingREST API with Spring BootSpring SecuritySpring Boot IntroductionSpring Data JPAValidation in Spring BootSpring Core ContainerSpring Framework IntroductionDynamic Programming in JavaGraph Data Structure in JavaHashing in JavaHeap (DSA)Linked List in JavaQueue in JavaRecursion in JavaSearching Algorithms in JavaSorting Algorithms in JavaStack in Java — DSA in JavaTime ComplexityTree Data Structure in JavaAdapter Design PatternBuilder Design PatternFactory Design PatternMVC Pattern — Java ProgrammingObserver Design PatternSingleton Design PatternArray Programs — PracticeBasic Java ProgramsCollection ProgramsJDBC ProgramsMultithreading ProgramsOOP ProgramsPlacement Coding QuestionsString Programs — PracticeBanking System — Java ProgrammingChat ApplicationE-Commerce BackendEmployee Management SystemLibrary Management System — Java ProgrammingSpring Boot Fullstack ProjectStudent Management System — Java ProgrammingCoding Interview QuestionsCollections Interview QuestionsCore Java Interview QuestionsJDBC Interview QuestionsMultithreading Interview QuestionsOOPs Interview QuestionsSpring Framework Interview QuestionsJava Cheat SheetImportant Formulas & ConceptsImportant Java ProgramsQuick Revision Notes — Java ProgrammingJava Master Course - Learning Roadmap
Complete guide to Java PriorityQueue — binary heap implementation, min-heap and max-heap, internal working, heapify operations, comparison with other queues, and practical applications.
What is PriorityQueue?
java.util.PriorityQueue is a queue where elements are dequeued based on priority (not insertion order). By default, it's a min-heap — the smallest element (by natural ordering or comparator) is always at the head.
java example
public class PriorityQueue<E>
extends AbstractQueue<E>
implements SerializableKey characteristics:
- Not FIFO — elements come out in priority order (smallest first by default)
- Backed by a binary heap (array-based)
- O(log n) for offer/poll, O(1) for peek
- Not thread-safe — use
PriorityBlockingQueuefor concurrency - No null elements
- No capacity limit (grows dynamically)
Time Complexity
| Operation | Time Complexity | Notes |
|---|---|---|
| ----------- | :-: | --- |
offer(E e) / add(E e) | O(log n) | Sift up |
poll() / remove() | O(log n) | Sift down |
peek() / element() | O(1) | Just return root |
remove(Object o) | O(n) | Linear search + sift |
contains(Object o) | O(n) | Linear search |
size() | O(1) | Stored field |
toArray() | O(n) | Copy array |
| Construction from collection | O(n) | Heapify (Floyd's algorithm) |
Why Construction is O(n), Not O(n log n)?
Building a heap from an unsorted array uses Floyd's bottom-up heapify, which runs in O(n) — more efficient than inserting elements one by one.
Basic Usage
java example
import java.util.*;
public class PriorityQueueDemo {
public static void main(String[] args) {
// Min-heap (default) — smallest first
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
minHeap.offer(40);
minHeap.offer(10);
minHeap.offer(30);
minHeap.offer(20);
minHeap.offer(50);
System.out.println("Peek (min): " + minHeap.peek()); // 10
System.out.println("\nPolling (ascending order):");
while (!minHeap.isEmpty()) {
System.out.print(minHeap.poll() + " ");
}
// Output: 10 20 30 40 50
// Max-heap — largest first
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Comparator.reverseOrder());
maxHeap.offer(40);
maxHeap.offer(10);
maxHeap.offer(30);
maxHeap.offer(20);
maxHeap.offer(50);
System.out.println("\n\nPolling (descending order):");
while (!maxHeap.isEmpty()) {
System.out.print(maxHeap.poll() + " ");
}
// Output: 50 40 30 20 10
}
}Output
PriorityQueue: [1, 3, 2, 5, 4] Peek (min): 1 Poll: 1 Poll: 2 Poll: 3 Poll: 4 Poll: 5 Max-Heap (reverse order): Poll: 5 Poll: 4 Poll: 3
Queue Interface Methods
| Operation | Throws Exception | Returns null/false |
|---|---|---|
| Insert | add(e) → IllegalStateException | offer(e) → false |
| Remove | remove() → NoSuchElementException | poll() → null |
| Examine | element() → NoSuchElementException | peek() → null |
For PriorityQueue, add() and offer() behave identically (no capacity limit), but offer() is preferred style.
Custom Priority with Comparator
Example
// Priority based on task urgency
record Task(String name, int priority) {}
PriorityQueue<Task> taskQueue = new PriorityQueue<>(
Comparator.comparingInt(Task::priority) // Lower number = higher priority
);
taskQueue.offer(new Task("Fix bug", 1));
taskQueue.offer(new Task("Write docs", 3));
taskQueue.offer(new Task("Code review", 2));
taskQueue.offer(new Task("Deploy", 1));
while (!taskQueue.isEmpty()) {
Task task = taskQueue.poll();
System.out.println("[P" + task.priority() + "] " + task.name());
}
Output:
Example
[P1] Fix bug
[P1] Deploy
[P2] Code review
[P3] Write docs
Practical Applications
1. Finding K Largest Elements
Example
public static List<Integer> findKLargest(int[] arr, int k) {
// Min-heap of size k — maintains k largest seen so far
PriorityQueue<Integer> minHeap = new PriorityQueue<>(k);
for (int num : arr) {
if (minHeap.size() < k) {
minHeap.offer(num);
} else if (num > minHeap.peek()) {
minHeap.poll();
minHeap.offer(num);
}
}
return new ArrayList<>(minHeap);
}
int[] data = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5};
System.out.println(findKLargest(data, 3)); // [5, 6, 9] (top 3)
Time: O(n log k) | Space: O(k)
2. Merge K Sorted Lists
Example
public static List<Integer> mergeKSorted(List<List<Integer>> lists) {
PriorityQueue<int[]> pq = new PriorityQueue<>(
Comparator.comparingInt(a -> a[0])
);
// Initialize with first element from each list
for (int i = 0; i < lists.size(); i++) {
if (!lists.get(i).isEmpty()) {
pq.offer(new int[]{lists.get(i).get(0), i, 0});
// [value, listIndex, elementIndex]
}
}
List<Integer> result = new ArrayList<>();
while (!pq.isEmpty()) {
int[] entry = pq.poll();
result.add(entry[0]);
int listIdx = entry[1];
int elemIdx = entry[2] + 1;
if (elemIdx < lists.get(listIdx).size()) {
pq.offer(new int[]{lists.get(listIdx).get(elemIdx), listIdx, elemIdx});
}
}
return result;
}
Time: O(N log k) where N = total elements, k = number of lists
3. Dijkstra's Shortest Path (Concept)
Example
// PriorityQueue naturally fits shortest path algorithms
PriorityQueue<int[]> pq = new PriorityQueue<>(
Comparator.comparingInt(a -> a[1]) // Sort by distance
);
pq.offer(new int[]{startNode, 0});
while (!pq.isEmpty()) {
int[] current = pq.poll();
int node = current[0], dist = current[1];
// Process neighbors, offer shorter paths...
}
4. Running Median
java example
public class RunningMedian {
// Max-heap for lower half
PriorityQueue<Integer> lower = new PriorityQueue<>(Comparator.reverseOrder());
// Min-heap for upper half
PriorityQueue<Integer> upper = new PriorityQueue<>();
public void addNumber(int num) {
lower.offer(num);
upper.offer(lower.poll()); // Balance: move max of lower to upper
if (upper.size() > lower.size()) {
lower.offer(upper.poll()); // Keep lower same or 1 larger
}
}
public double getMedian() {
if (lower.size() > upper.size()) {
return lower.peek();
}
return (lower.peek() + upper.peek()) / 2.0;
}
}Important Behaviors
Iteration Order ≠ Priority Order!
java example
PriorityQueue<Integer> pq = new PriorityQueue<>(Arrays.asList(5, 1, 3, 2, 4));
// WRONG — iterator does NOT return elements in priority order!
for (int num : pq) {
System.out.print(num + " ");
}
// Output might be: 1 2 3 5 4 (heap order, NOT sorted!)
// CORRECT — poll() gives priority order
while (!pq.isEmpty()) {
System.out.print(pq.poll() + " ");
}
// Output: 1 2 3 4 5 (sorted)No Random Access
java example
// Can't access element at index — it's a queue, not a list
// pq.get(2); // No such method!Constructors
java example
// Default min-heap, initial capacity 11
PriorityQueue<Integer> pq1 = new PriorityQueue<>();
// Custom initial capacity
PriorityQueue<Integer> pq2 = new PriorityQueue<>(100);
// Custom comparator (max-heap)
PriorityQueue<Integer> pq3 = new PriorityQueue<>(Comparator.reverseOrder());
// From collection (O(n) heapify)
PriorityQueue<Integer> pq4 = new PriorityQueue<>(Arrays.asList(5, 3, 8, 1, 2));
// Capacity + Comparator
PriorityQueue<String> pq5 = new PriorityQueue<>(10,
Comparator.comparingInt(String::length));Thread Safety
java example
// PriorityQueue is NOT thread-safe
// Option 1: PriorityBlockingQueue (concurrent, unbounded)
BlockingQueue<Integer> pbq = new PriorityBlockingQueue<>();
pbq.put(5); // Never blocks (unbounded)
int val = pbq.take(); // Blocks if empty
// Option 2: Synchronized wrapper (less efficient)
Queue<Integer> syncQ = new PriorityQueue<>();
// No Collections.synchronizedQueue() — use PriorityBlockingQueue insteadCommon Mistakes
1. Assuming Iterator Gives Sorted Output
java example
// WRONG — forEach/iterator doesn't give sorted order!
pq.forEach(System.out::println); // Not in priority order!
// CORRECT — poll() gives sorted order
while (!pq.isEmpty()) System.out.println(pq.poll());2. Adding Null
java example
pq.offer(null); // NullPointerException!3. Modifying Elements After Adding
java example
// If you change an element's priority after it's in the queue,
// the heap property is violated!
Task task = new Task("bug", 3);
pq.offer(task);
task.setPriority(1); // Heap doesn't know about this change!
// Fix: remove and re-add
pq.remove(task);
task.setPriority(1);
pq.offer(task);4. Confusing with Sorting
java example
// PriorityQueue is NOT for sorting a list
// Use Collections.sort() or Arrays.sort() for that
// PriorityQueue is for dynamic "always know the min/max" scenariosPriorityQueue vs TreeSet
| Feature | PriorityQueue | TreeSet |
|---|---|---|
| Purpose | Access minimum quickly | All sorted, unique elements |
| Duplicates | Allowed | Not allowed |
| peek()/first() | O(1) | O(log n) |
| offer()/add() | O(log n) | O(log n) |
| remove(element) | O(n) | O(log n) |
| Iteration order | NOT sorted | Sorted |
| Range queries | No | Yes (subSet, etc.) |
Interview Questions
Q1: How does PriorityQueue work internally?
A: It uses a binary min-heap stored in an array. The smallest element is always at index 0 (root). Insert uses sift-up, remove uses sift-down to maintain the heap property.
Q2: What is the time complexity of PriorityQueue operations?
A: offer/poll: O(log n), peek: O(1), remove(Object): O(n), contains: O(n).
Q3: Does iterating a PriorityQueue give sorted output?
A: No! The iterator traverses the internal array (heap order), not priority order. Only poll() returns elements in priority order.
Q4: How do you create a max-heap PriorityQueue?
A: Use new PriorityQueue<>(Comparator.reverseOrder()) or new PriorityQueue<>((a, b) -> b - a).
Q5: Can PriorityQueue contain null or duplicates?
A: No nulls (NullPointerException). Yes duplicates (it's not a Set).
Q6: What is the difference between PriorityQueue and PriorityBlockingQueue?
A: PriorityBlockingQueue is thread-safe and supports blocking operations (take() blocks when empty). PriorityQueue is not thread-safe and not blocking.
Q8: Why does printing PriorityQueue not show elements in sorted order?
A: PriorityQueue is backed by a binary min-heap, which only guarantees that the root (index 0) is the minimum element. The internal array representation doesn't store elements in fully sorted order — only the heap property is maintained. To get sorted order, you must repeatedly call poll().
Q9: How do you create a max-heap PriorityQueue?
A: Pass Comparator.reverseOrder() or Collections.reverseOrder() to the constructor: new PriorityQueue<>(Comparator.reverseOrder()). Or use a custom comparator: new PriorityQueue<>((a, b) -> b - a). This makes poll() return the maximum element instead of minimum.
Q10: What is the time complexity of PriorityQueue operations?
A: offer()/add(): O(log n) — element bubbles up. poll()/remove(): O(log n) — root removed, last element sifts down. peek(): O(1) — just returns root. contains(): O(n) — linear scan. remove(Object): O(n) — find element + O(log n) restructure.
Q11: Can PriorityQueue contain duplicate elements?
A: Yes! Unlike Set implementations, PriorityQueue allows duplicate elements. Multiple elements with the same priority coexist in the heap. However, null elements are NOT allowed (throws NullPointerException).
Q12: What is the difference between PriorityQueue and TreeSet?
A: PriorityQueue: allows duplicates, only guarantees min/max at head, O(log n) insert/remove, O(n) for arbitrary element. TreeSet: no duplicates, ALL elements sorted, O(log n) for all operations including arbitrary access, supports range queries. Use PriorityQueue for producer-consumer; TreeSet for sorted unique collection.
Summary
| Aspect | PriorityQueue |
|---|---|
| Structure | Binary heap (array-based) |
| Default order | Min-heap (smallest first) |
| peek() | O(1) — instant access to minimum |
| offer()/poll() | O(log n) |
| Iteration | NOT in priority order |
| Null | Not allowed |
| Duplicates | Allowed |
| Thread-safe | No (use PriorityBlockingQueue) |
| Best for | Top-K problems, scheduling, Dijkstra |
Exam Focus
Revise definitions, diagrams, examples, and short-answer points for PriorityQueue in Java.
Interview Use
Prepare one clear explanation, one practical example, and one common mistake for this Java Master Course topic.
Search Terms
java-master-course, java master course, java, master, course, collections, framework, queue
Related Java Master Course Topics
Continue learning this concept
Collections FrameworkArrayDeque in JavaComplete guide to Java ArrayDeque — circular array implementation, resizing strategy, performance advantages over LinkedList and Stack, internal working, and practical usage patterns.Collections FrameworkDeque Interface in JavaComplete guide to Java Deque interface — double-ended queue operations, stack and queue usage, method families, comparison of implementations, and best practices.Collections FrameworkCollections Framework OverviewComplete guide to Java Collections Framework covering hierarchy, interfaces, implementations, algorithms, and choosing the right collection for your use case.Collections FrameworkCollections Practice ProgramsComprehensive Java Collections practice programs covering List, Set, Map, Queue operations with solutions, explanations, and time complexity analysis.Collections FrameworkComparable vs Comparator in JavaDeep dive into Comparable and Comparator interfaces in Java — natural ordering, custom sorting, lambda expressions, method references, and practical comparisons with examples.Collections FrameworkGenerics in JavaComplete guide to Java Generics — type parameters, bounded types, wildcards, type erasure, generic methods, generic classes, and common patterns with practical examples.