Min-max heaps: remove either end of one dispatch priority array

Last updated: 4 Oct 20269 min read

tutorial

A min-max heap is one complete binary tree stored in an array. Its root is a minimum level; children are maximum level; grandchildren return to minimum level, and the pattern alternates. Every minimum-level node is no greater than its descendants, while a maximum-level node is no smaller. The global minimum is at the root. The global maximum is among its two children. Insertion compares the new key with its parent, then bubbles along grandparents of the appropriate level. Removing an extreme replaces its slot with the last array item and trickles through children or grandchildren; a grandchild swap may need a parent correction to preserve the opposite-level order. Duplicate priorities are allowed and one instance is removed at a time. The model offers both extremes, not arbitrary removal, keyed decrease-priority, or stable first-in-first-out order among ties.

Operational case

Insert priorities 47, 19, 61, 29, 83, 37, and another 47. The minimum is 19 and the maximum is 83. Removing one of each leaves five entries with minimum 29 and maximum 61. The two 47 entries remain distinct array items even though their values compare equal. A pop from an empty queue returns no value, and a one-item queue reports the same key as both ends. When removing a maximum from one of the root's children, the last item may be smaller than the root; the implementation exchanges them before max-level trickling so the minimum-level rule remains intact. Array positions are transient after any insertion or removal.

Working Python program

class DispatchPriorityEnds:
    def __init__(self):
        self.values = []

    @staticmethod
    def _minimum_level(position):
        return ((position + 1).bit_length() - 1) % 2 == 0

    def _bubble(self, position, minimum):
        while position >= 3:
            grandparent = (position - 3) // 4
            better = self.values[position] < self.values[grandparent] if minimum else self.values[position] > self.values[grandparent]
            if not better:
                break
            self.values[position], self.values[grandparent] = self.values[grandparent], self.values[position]
            position = grandparent

    def add(self, priority):
        self.values.append(priority)
        position = len(self.values) - 1
        if position == 0:
            return
        parent = (position - 1) // 2
        minimum = self._minimum_level(position)
        crosses = self.values[position] > self.values[parent] if minimum else self.values[position] < self.values[parent]
        if crosses:
            self.values[position], self.values[parent] = self.values[parent], self.values[position]
            self._bubble(parent, not minimum)
        else:
            self._bubble(position, minimum)

    def _trickle(self, position, minimum):
        while 2 * position + 1 < len(self.values):
            candidates = [child for child in (2 * position + 1, 2 * position + 2,
                                               4 * position + 3, 4 * position + 4,
                                               4 * position + 5, 4 * position + 6)
                          if child < len(self.values)]
            chosen = min(candidates, key=self.values.__getitem__) if minimum else max(candidates, key=self.values.__getitem__)
            better = self.values[chosen] < self.values[position] if minimum else self.values[chosen] > self.values[position]
            if not better:
                break
            self.values[position], self.values[chosen] = self.values[chosen], self.values[position]
            if chosen >= 4 * position + 3:
                parent = (chosen - 1) // 2
                crosses = self.values[chosen] > self.values[parent] if minimum else self.values[chosen] < self.values[parent]
                if crosses:
                    self.values[chosen], self.values[parent] = self.values[parent], self.values[chosen]
                position = chosen
            else:
                break

    def minimum(self):
        return None if not self.values else self.values[0]

    def maximum(self):
        if not self.values:
            return None
        if len(self.values) == 1:
            return self.values[0]
        return max(self.values[1:3])

    def pop_minimum(self):
        if not self.values:
            return None
        result = self.values[0]
        last = self.values.pop()
        if self.values:
            self.values[0] = last
            self._trickle(0, True)
        return result

    def pop_maximum(self):
        if not self.values:
            return None
        if len(self.values) == 1:
            return self.values.pop()
        position = 1 if len(self.values) == 2 or self.values[1] >= self.values[2] else 2
        result = self.values[position]
        last = self.values.pop()
        if position < len(self.values):
            self.values[position] = last
            if self.values[position] < self.values[0]:
                self.values[position], self.values[0] = self.values[0], self.values[position]
            self._trickle(position, False)
        return result


if __name__ == "__main__":
    queue = DispatchPriorityEnds()
    for priority in [47, 19, 61, 29, 83, 37, 47]:
        queue.add(priority)
    print(queue.minimum(), queue.maximum())
    print(queue.pop_minimum(), queue.pop_maximum())
    print(queue.minimum(), queue.maximum(), len(queue.values))

Output

19 83
19 83
29 61 5

Time, space, and tradeoff

The two extremes are found in O(1) time, and insertion or either pop moves along O(log N) levels. Trickle-down examines at most six descendants per visited node, so the work per level is bounded. The array uses O(N) space and no second synchronized heap or tombstone map. This program inserts items one at a time, costing O(N log N) to build from N priorities; it does not implement the separate linear-time bulk-heapify method. A two-heap double-ended queue can offer the same endpoint operations with stale-entry bookkeeping, while this one maintains one alternating-level array. For stable ties or ID-based updates, add an explicit payload and handle policy.

Common Mistakes

Do not apply a normal min-heap sift to maximum levels.
Do not forget to repair the opposite-level parent after a grandchild swap.
Do not claim equal priorities preserve insertion order.
Do not call array positions durable handles after a pop.

Connected lessons

Compare this operation boundary with Persistent range MEX: search last occurrences in prefix versions, Range XOR bases: merge linear spans in a segment tree, Affine lazy segment trees: compose range calibration before summing, then complete the audit project and decision quiz.

data structures

trees-and-heaps