extractMinMax

extractminmax is an operation in data structures that manage ordered collections, particularly double-ended priority queues and min-max heaps. It returns and removes both the current minimum and the current maximum element from the structure, yielding the two extreme values in an unspecified order. This contrasts with separate operations extractMin or extractMax, which retrieve only one extreme at a time.

In a double-ended priority queue, extractMin and extractMax are standard operations; extractMinMax can be implemented either by performing two successive extractions or by a specialized routine designed to remove both extremes with fewer structural adjustments. In min-max heaps, a single structure simultaneously maintains the minimum and maximum elements using alternating min and max levels. The minimum is at the root, and the maximum is among a small set of candidates at the bottom level. Removing both requires reordering to preserve both the min-heap and max-heap properties; the typical cost is O(log n) per removed element, so two removals yield O(log n) overall, with potential constant-factor optimizations in a combined method.

Applications include algorithms that need both ends of a dataset, such as certain scheduling, selection, or streaming analyses where extremes are processed in pairs. Availability of extractminmax varies by library; some deployments expose it as a distinct operation, while others implement it via two calls to extractMin and extractMax. See also min-heap, max-heap, min-max heap, and double-ended priority queue.