Skip to content
AITroveRead. Build. Understand.
Reading list
Make this comfortable

Double-ended queues: reconcile min and max heaps

Last updated: 5 Oct 20269 min read
tutorial
IntermediateBy AITrove Editorial

A double-ended priority queue must remove the lowest or highest priority on demand. This design stores each incident in a min-heap and max-heap and keeps one exact live map keyed by incident ID. Removing from one heap deletes its live-map record; the matching entry in the other heap becomes stale and is skipped when encountered. Arrival numbers make equal-priority removal deterministic and prevent an old entry from matching a later reuse of the same ID. When heap entries grow too far beyond live records, both heaps are rebuilt from the live map. It is a practical twin-heap design, not a min-max heap with alternating tree levels. Duplicate live IDs are rejected.

Operational case

Four incidents have priorities 47, 19, 61, and 19. Pop-min returns the first priority-19 arrival, valve-19. Pop-max then returns priority-61 sensor-61. Both removed incidents leave stale entries in the opposite heap, but the live map prevents either from being returned twice. Reusing a removed incident ID creates a new arrival number; a stale earlier heap record cannot masquerade as the new one. Without periodic rebuilding, a workload alternating additions and removals at one end can retain an arbitrarily large opposing heap even when few incidents remain live.

Working Python program

python
import heapq
import itertools


class DualEndedIncidentQueue:
    def __init__(self):
        self.minimum = []
        self.maximum = []
        self.live = {}
        self.sequence = itertools.count()

    def _compact_if_needed(self):
        if len(self.minimum) + len(self.maximum) <= 3 * len(self.live) + 32:
            return
        self.minimum = [(priority, arrival, incident_id)
                        for incident_id, (priority, arrival) in self.live.items()]
        self.maximum = [(-priority, arrival, incident_id)
                        for incident_id, (priority, arrival) in self.live.items()]
        heapq.heapify(self.minimum)
        heapq.heapify(self.maximum)

    def push(self, priority, incident_id):
        if incident_id in self.live:
            raise ValueError("incident already queued")
        arrival = next(self.sequence)
        self.live[incident_id] = (priority, arrival)
        heapq.heappush(self.minimum, (priority, arrival, incident_id))
        heapq.heappush(self.maximum, (-priority, arrival, incident_id))
        self._compact_if_needed()

    def _pop(self, heap, sign):
        while heap:
            stored_priority, arrival, incident_id = heapq.heappop(heap)
            priority = sign * stored_priority
            if self.live.get(incident_id) == (priority, arrival):
                del self.live[incident_id]
                self._compact_if_needed()
                return priority, incident_id
        raise IndexError("empty priority queue")

    def pop_min(self):
        return self._pop(self.minimum, 1)

    def pop_max(self):
        return self._pop(self.maximum, -1)


queue = DualEndedIncidentQueue()
for priority, incident_id in ((47, "pump-47"), (19, "valve-19"),
                              (61, "sensor-61"), (19, "grid-83")):
    queue.push(priority, incident_id)
print("min=", queue.pop_min(), "max=", queue.pop_max(),
      "remaining=", len(queue.live), sep="")

Output

Output
min=(19, 'valve-19')max=(61, 'sensor-61')remaining=2

Time, space, and tradeoff

Each insertion adds one entry to each heap, O(log N) time. A removal may skip many stale entries or trigger O(N) heap rebuilding, so one call has O(N log N) conservative worst-case work; across a long sequence, each stale entry is discarded once and threshold rebuilds amortize the cleanup. After a mutation, the threshold keeps stored heap entries O(L+1) for L live IDs, with a fixed small allowance. The exact live map means O(L) key storage as well, unlike an approximate membership structure. If memory or latency spikes cannot be accepted, use an indexed double-ended heap with stricter update rules. This example is single-threaded.

Common Mistakes

  • Do not return a stale entry from the opposite heap.
  • Do not match a reused ID without checking its arrival generation.
  • Do not claim every removal has logarithmic worst-case latency.
  • Do not omit a compaction policy when stale entries can accumulate.

Connected lessons

Compare its queue operations with Pairing heaps: meld roots and pair children on removal, Binomial heaps: carry equal-degree trees during merge, Radix heaps: queue nondecreasing integer priorities, then run the priority-queue audit and contract quiz.

Min-max heaps: remove either end of one dispatch priority array examines a related structure with a different operation boundary.

Sliding medians: expire heap entries by event identity examines a related structure with a different operation boundary.

data structures
trees-and-heaps
Storage details