# Guava MinMaxPriorityQueue: Complete Guide to Double-Ended Priority Queues in Java > Explore Guava MinMaxPriorityQueue, a Java double-ended priority queue. Get O(1) access to min/max elements with O(log n) insertions/deletions. Learn its use cases. - Repository: [Google/guava](https://github.com/google/guava) - Tags: deep-dive - Published: 2026-08-08 --- **Guava's `MinMaxPriorityQueue` is a double-ended priority queue implementation that provides O(1) access to both the smallest and largest elements while maintaining O(log n) time for insertions and deletions.** The `MinMaxPriorityQueue` class in Google's Guava library solves a critical gap in Java's standard collections by extending `AbstractQueue` to support bidirectional extremity access. Unlike `java.util.PriorityQueue`, which only efficiently retrieves the minimum element, this implementation in `com.google.common.collect` uses a sophisticated dual-heap structure packed into a single backing array. It enables constant-time retrieval of both ends of the priority spectrum, making it ideal for sliding windows, bounded caches, and scheduling systems that occasionally need the highest-priority item. ## Core Architecture in MinMaxPriorityQueue.java The implementation resides in [`guava/src/com/google/common/collect/MinMaxPriorityQueue.java`](https://github.com/google/guava/blob/main/guava/src/com/google/common/collect/MinMaxPriorityQueue.java) and employs a **min-max heap** structure that interleaves min-heap and max-heap levels within one physical array. ### Dual-Heap Design The queue maintains two logical heaps—`minHeap` and `maxHeap`—within the same `queue` array. Even-indexed levels (0, 2, 4...) follow min-heap ordering, while odd-indexed levels follow max-heap ordering. This structure allows **O(1)** lookups for both `peek()` (minimum) and `peekLast()` (maximum) without duplicating storage overhead. The `Heap` inner class encapsulates the heap logic, with instances cross-linked in the constructor to share the backing array. Elements determine their heap membership through the `isEvenLevel` method, which dictates whether `compareElements` uses direct or inverted comparison logic. ### Heap Operations Insertion invokes `bubbleUp` to propagate new elements through the appropriate heap levels, alternating comparisons based on level parity. Deletion employs `fillHole` to replace removed elements by pulling up the smallest grandchild, then uses `crossOver` and `crossOverUp` to maintain heap invariants across level boundaries. These operations execute in **O(log n)** time, traversing at most the height of the heap. Capacity management occurs through `growIfNeeded`, which doubles the array size for small queues or increases capacity by 1.5× for larger ones, optimizing memory allocation patterns. ## Configuration Options and Eviction ### Fluent Builder API Configuration proceeds through the nested `Builder` class, accessible via `MinMaxPriorityQueue.orderedBy(comparator)`. You can specify an expected size for initial capacity planning or define a `maximumSize` limit that triggers automatic eviction. ### Automatic Eviction Behavior When `maximumSize` is set, every `offer` operation checks the current size against the bound. If the queue exceeds its limit, the implementation automatically removes the greatest element via `pollLast()`. This behavior, documented in the class Javadoc at lines 69-72 of the source file, eliminates manual management when maintaining only the N smallest items. ## Practical Use Cases for MinMaxPriorityQueue Use this data structure when you need **bidirectional extremity access**. Common scenarios include: - **Sliding window algorithms** that must discard the current maximum while still processing the minimum - **Bounded caches** that retain only the N lowest-priority items (e.g., keeping the N cheapest bids) while evicting higher-priority entries - **Dual-ended priority operations** where you occasionally need to pop the greatest element without scanning the entire structure - **Memory-efficient double-ended queues** that avoid the overhead of maintaining two separate heap structures If you only access one end of the queue, prefer `PriorityQueue` for better performance. The extra bookkeeping in `MinMaxPriorityQueue` adds overhead when dual access isn't required. ## Code Examples ### Basic Double-Ended Operations ```java import com.google.common.collect.MinMaxPriorityQueue; MinMaxPriorityQueue queue = MinMaxPriorityQueue.create(); queue.offer(5); queue.offer(1); queue.offer(9); queue.offer(3); int min = queue.peek(); // Returns 1 int max = queue.peekLast(); // Returns 9 queue.poll(); // Removes 1 queue.pollLast(); // Removes 9 ``` ### Bounded Queue with Automatic Eviction ```java MinMaxPriorityQueue bounded = MinMaxPriorityQueue .orderedBy(Comparator.naturalOrder()) .maximumSize(5) .create(); for (int i = 10; i >= 1; i--) { bounded.offer(i); // Automatically evicts greatest when size exceeds 5 } // Result contains [1, 2, 3, 4, 5] ``` ### Custom Comparator Usage ```java Comparator byLength = Comparator.comparingInt(String::length); MinMaxPriorityQueue queue = MinMaxPriorityQueue .orderedBy(byLength) .create(); queue.addAll(List.of("a", "abcd", "ab", "abcde")); String shortest = queue.peek(); // Returns "a" String longest = queue.peekLast(); // Returns "abcde" ``` ## Performance Characteristics Iteration uses `QueueIterator`, which traverses elements in no particular order while maintaining fail-fast behavior on concurrent modifications. The single-array storage avoids memory overhead but introduces slight constant-factor costs due to level-aware comparisons. While `peek()` and `peekLast()` operate in constant time, insertion and removal remain logarithmic. For large, unbounded queues, `MinMaxPriorityQueue` can be slower than `PriorityQueue` due to the extra bookkeeping required for dual-heap maintenance. ## Summary - **MinMaxPriorityQueue** provides O(1) access to both minimum and maximum elements via `peek()` and `peekLast()` - Implements a dual-heap structure (min-heap on even levels, max-heap on odd levels) in [`guava/src/com/google/common/collect/MinMaxPriorityQueue.java`](https://github.com/google/guava/blob/main/guava/src/com/google/common/collect/MinMaxPriorityQueue.java) - Supports bounded collections with automatic eviction of greatest elements using `maximumSize` and `pollLast()` - Offers `Builder` configuration for custom comparators and capacity planning through `orderedBy()` and `expectedSize()` - Ideal for sliding windows, bounded caches, and any scenario requiring dual-ended priority operations ## Frequently Asked Questions ### How does MinMaxPriorityQueue differ from Java's PriorityQueue? `java.util.PriorityQueue` only provides efficient access to the head (minimum) element. `MinMaxPriorityQueue` extends `AbstractQueue` to offer both `peek()`/`poll()` for the minimum and `peekLast()`/`pollLast()` for the maximum, both in O(1) time for access. The trade-off is slightly higher overhead due to the interleaved heap structure and `crossOver` logic required to maintain both invariants simultaneously. ### When should I use the maximumSize parameter? Use `maximumSize` when implementing bounded collections that must retain only the N lowest-priority elements. As implemented in the source code, setting this parameter causes `offer()` to automatically call `pollLast()` to evict the greatest element when the queue exceeds its bound. This is perfect for maintaining "top N smallest items" (such as lowest bids or earliest timestamps) without writing manual removal logic after each insertion. ### Is MinMaxPriorityQueue thread-safe? No, this implementation is not thread-safe. Like standard Java collections such as `ArrayList` and `HashMap`, it requires external synchronization if accessed concurrently. The `QueueIterator` provides fail-fast behavior to detect concurrent modifications during iteration, throwing `ConcurrentModificationException` if the queue is structurally modified during traversal. ### What is the time complexity of MinMaxPriorityQueue operations? Accessing either extremity via `peek()` or `peekLast()` takes O(1) time. Insertions via `offer()` and deletions via `poll()` or `pollLast()` execute in O(log n) time. The underlying `bubbleUp` and `fillHole` operations traverse at most the height of the heap, maintaining logarithmic guarantees regardless of whether you're extracting the minimum or maximum element.