如何实现支持push(x)、pop()和pop_max()方法的队列并优化时间复杂度？

Great question—you’re already thinking in the right direction by weighing tradeoffs between your two initial implementations. Let’s break down how we can get closer to optimal time complexity for all three operations.

First, let’s recap your existing approaches to ground our discussion:

• Basic Queue + Auxiliary Queue: Fast push()/pop() (O(1)) but pop_max() requires scanning the entire queue (O(n))—not ideal for large datasets where pop_max() is frequent.
• Doubly Linked List + Monotonic Stack: Fast pop()/pop_max() (O(1)) but push() requires reordering the stack to maintain monotonicity (O(n))—a dealbreaker if you’re pushing elements often.

A Better Approach: Doubly Linked List + Priority Queue (Heap) + Timestamp Tracking #

We can combine three components to balance all three operations, aiming for O(log n) time for push() and amortized O(log n) for pop_max(), with pop() remaining O(1). Here’s how it works:

Core Components

1. Doubly Linked List: Stores the actual queue elements, allowing O(1) deletion of any node (once we have a reference to it). Each node includes:

   • The element value
   • Pointers to previous/next nodes
   • A boolean flag is_deleted to mark if the node has been removed (to handle stale entries in the heap)
   • We also track the head and tail of the list for fast push() and pop().

2. Max-Heap (Priority Queue): Stores entries to quickly locate the largest element. Each heap entry is a tuple (-value, timestamp, node):

   • We use -value because many built-in heaps are min-heaps (this lets us simulate a max-heap)
   • timestamp is an incrementing integer assigned to each element on push()—this ensures that if multiple elements have the same max value, the earliest one (smallest timestamp) is prioritized (critical for your FIFO pop_max() requirement)
   • node is a direct reference to the corresponding node in the doubly linked list.

3. Global Timestamp Counter: Increments every time we push() an element, ensuring unique, ordered timestamps.

Operation Breakdown

• push(x):

  1. Create a new doubly linked list node with value x, add it to the tail of the list.
  2. Assign the current timestamp to the node, then push (-x, timestamp, node) into the heap.
  3. Increment the timestamp counter.
  • Time Complexity: O(log n) (heap insertion is O(log n), linked list append is O(1)).

• pop():

  1. If the queue is empty, return an error or null.
  2. Grab the head node, mark it as is_deleted = true.
  3. Update the list’s head pointer to the node’s next element (if it exists).
  4. Return the node’s value.
  • Time Complexity: O(1) (linked list head deletion and flagging are constant-time operations). We don’t need to modify the heap here—stale heap entries will be filtered out later during pop_max().

• pop_max():

  1. If the queue is empty, return an error or null.
  2. Continuously pop elements from the heap until we find one where node.is_deleted = false (this skips any nodes already removed by pop() or previous pop_max() calls).
  3. Mark this valid node as is_deleted = true.
  4. Remove the node from the linked list:
     • If it’s the head, update the head pointer to its next node.
     • If it’s the tail, update the tail pointer to its previous node.
     • Otherwise, adjust the previous/next pointers of adjacent nodes to bypass it.
  5. Return the node’s value.
  • Time Complexity: Amortized O(log n). Each node is pushed to the heap exactly once and popped exactly once, so the total heap operations across all pop_max() calls are O(n log n). Even if we have to skip stale entries, each stale entry is processed only once.

Why the "get_min Queue" Approach Doesn’t Apply #

You mentioned the classic queue with constant-time get_min()—that uses a monotonic auxiliary queue to track minimums. However, this approach falls apart for pop_max() because:

• The monotonic queue only tracks the order of minima/maxima, not the actual positions of elements in the main queue.
• Deleting an arbitrary element (like the earliest max) would require re-building the monotonic queue, which brings us back to O(n) time. The structure isn’t designed for arbitrary deletions.

Final Notes #

This approach strikes a great balance for most use cases: pop() stays blazingly fast, push() is logarithmic, and pop_max() is amortized logarithmic. If your workload has extremely frequent push() operations, you might need to weigh tradeoffs, but this is the closest you’ll get to "optimal" for all three operations.

内容的提问来源于stack exchange，提问作者sugarfree