Guava MinMaxPriorityQueue: Complete Guide to Double-Ended Priority Queues in Java

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<E> 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 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

import com.google.common.collect.MinMaxPriorityQueue;

MinMaxPriorityQueue<Integer> 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

MinMaxPriorityQueue<Integer> bounded = MinMaxPriorityQueue
    .<Integer>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

Comparator<String> byLength = Comparator.comparingInt(String::length);
MinMaxPriorityQueue<String> 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
• 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.

{
  "mcpServers": {
    "instagit": {
      "command": "npx",
      "args": ["-y", "instagit@latest"]
    }
  }
}