Monotonic Queue vs Priority Queue: When to Use Each

For sliding window maximum, you have two choices: monotonic queue (O(n)) or priority queue (O(n log k)).

The winner: Monotonic queue is asymptotically faster.

This guide shows you when to use each and why.

TL;DR

Monotonic Queue (Deque):

• Time: O(n) ✨
• Space: O(k)
• Use for: Sliding window max/min

Priority Queue (Heap):

• Time: O(n log k)
• Space: O(k)
• Use for: K-th largest, median, general priority

For sliding window max/min, always prefer monotonic queue.

Performance Comparison

Monotonic Queue Approach

from collections import deque

def maxSlidingWindow_deque(nums, k):
    """
    Monotonic queue approach.
    
    Time: O(n) ✨
    Space: O(k)
    """
    result = []
    dq = deque()
    
    for i in range(len(nums)):
        # Remove out-of-window
        while dq and dq[0] < i - k + 1:
            dq.popleft()
        
        # Maintain decreasing order
        while dq and nums[i] > nums[dq[-1]]:
            dq.pop()
        
        dq.append(i)
        
        if i >= k - 1:
            result.append(nums[dq[0]])
    
    return result

Priority Queue Approach

import heapq

def maxSlidingWindow_heap(nums, k):
    """
    Priority queue approach.
    
    Time: O(n log k)
    Space: O(k)
    """
    result = []
    heap = []  # Max heap (use negative values)
    
    for i in range(len(nums)):
        # Add current element
        heapq.heappush(heap, (-nums[i], i))
        
        # Remove out-of-window elements
        while heap[0][1] < i - k + 1:
            heapq.heappop(heap)
        
        if i >= k - 1:
            result.append(-heap[0][0])
    
    return result

When to Use Each

Use Monotonic Queue When:

• ✅ Sliding window maximum or minimum
• ✅ Want optimal O(n) time
• ✅ Interview (shows advanced knowledge)

Use Priority Queue When:

• ✅ Need K-th largest/smallest (not just max/min)
• ✅ Need median (use two heaps)
• ✅ Merge K sorted arrays
• ✅ General priority management
• ✅ Simplicity over optimal complexity

Real-World Performance

For n=100,000, k=1,000:

• Monotonic queue: ~200,000 operations (O(n))
• Priority queue: ~1,700,000 operations (O(n log k))

Speedup: ~8.5× faster with monotonic queue

Conclusion

For sliding window max/min:

• Always use monotonic queue (O(n) vs O(n log k))

For other problems:

• Use priority queue (K-th largest, median, etc.)

The rule:

• Sliding window max/min → Monotonic queue ✨
• Everything else → Priority queue

Next steps:

• Monotonic Queue Template
• Sliding Window Max Mistakes
• Complete Guide