|

Swift Collections: Two Ends of One Priority Queue

Two ends of a priority queue represented by a heap

A scheduler can tell you which job has the earliest deadline. A monitoring tool can tell you which measurement is the largest. But sometimes the same queue must answer both questions about its own values: what is smallest, and what is largest? Keeping a sorted array makes the answers easy, but inserting a new value can shift many elements. Sorting again after every update is even less attractive.

The Heap type in Swift Collections takes a different approach. It keeps a partial order rather than a sorted sequence, so it can expose both extremes without maintaining every element in sorted order. Its implementation is a min-max heap, not the more familiar heap that optimizes only one end.

This article follows the two-level ordering rule, the way insertion and removal repair that rule, and the API decisions that prevent callers from depending on an accidental iteration order. The examples use the public HeapModule API from the 1.2.1 source tag.

Two extremes without sorting everything

import HeapModule

var queue = Heap([7, 2, 9, 4])
print("min:", queue.min ?? -1)
print("max:", queue.max ?? -1)
queue.insert(1)
print("after insert:", queue.min ?? -1)
print("remove max:", queue.popMax() ?? -1)
print("remaining max:", queue.max ?? -1)
min: 2
max: 9
after insert: 1
remove max: 9
remaining max: 7

The initial values are 7, 2, 9, and 4. The smallest is 2, and the largest is 9. Inserting 1 changes the minimum without changing the maximum. After popMax() removes 9, the largest remaining value is 7. The ?? -1 fallback makes the printed values nonoptional; it is not part of the heap’s ordering behavior.

A Heap<Element> requires Element: Comparable. The min and max properties return optionals because an empty heap has no extreme. The implementation documents O(1) access to both, while insert, popMin, and popMax require O(log n) comparisons. Those are algorithmic bounds, not measured timings for this example.

Alternating levels do the work

A binary min-heap places the smallest value at the root. A min-max heap alternates responsibilities: nodes on even-numbered levels are no greater than their descendants, while nodes on odd-numbered levels are no smaller than their descendants. The root therefore holds the minimum. When there are at least three elements, the maximum is the larger of the root’s two children.

The source stores this complete binary tree in a single ContiguousArray, in breadth-first order. There are no separately allocated tree nodes. The max implementation handles heaps with zero, one, or two elements separately, then compares positions 1 and 2 when at least three elements exist.

Insertion appends a value and calls bubbleUp to restore the alternating invariant. Removing an extreme replaces the vacated position with a value from the end of storage, then repairs the affected min or max level with a downward operation. The source names these operations bubbleUp, trickleDownMin, and trickleDownMax. The key trade-off is deliberate: the internal array is only partially ordered, but either extreme remains cheap to find.

The implementation also provides init(_ elements: some Sequence<Element>). Instead of inserting each input independently, it builds storage from the sequence and heapifies it. Its documented complexity is O(n), which is useful when a queue starts with an existing batch.

An empty heap is a normal state

import HeapModule

var queue = Heap<Int>()
print("empty:", queue.isEmpty)
print("first:", queue.popMin() as Any)
queue.insert(5)
print("single min:", queue.min ?? -1)
print("single max:", queue.max ?? -1)
print("taken:", queue.popMin() ?? -1)
print("empty again:", queue.isEmpty)
empty: true
first: nil
single min: 5
single max: 5
taken: 5
empty again: true

Here popMin() returns nil on the empty heap. After inserting 5, the same element is both the minimum and the maximum. Removing it returns the heap to the empty state. The cast to Any in the first print is only to make the optional’s representation explicit.

There are also removeMin() and removeMax() methods, but these require a nonempty heap and force-unwrap their corresponding pop results. For a queue that may run dry, the optional-returning popMin() and popMax() are the safer interface. The source tests cover empty and small heaps as well as larger ordering cases.

Why Heap is not a Collection

A tempting API would let callers loop through a heap as if its storage were sorted. That would turn an implementation detail into a promise. Heap deliberately does not conform to Sequence or Collection. Its unordered property exposes a read-only array view, but its order is explicitly unspecified and may change across library versions.

import HeapModule

let queue = Heap([8, 3, 6, 1])
print("count:", queue.count)
print("members:", queue.unordered.sorted())
var draining = queue
var ascending: [Int] = []
while let value = draining.popMin() {
  ascending.append(value)
}
print("ascending:", ascending)
print("original count:", queue.count)
count: 4
members: [1, 3, 6, 8]
ascending: [1, 3, 6, 8]
original count: 4

The call to sorted() makes the membership display deterministic; printing queue.unordered directly would not. Repeatedly popping the minimum from draining produces ascending values, but it consumes that copy of the heap. The original queue still contains four elements because Heap is a value type.

This distinction matters when debugging. If you need a stable sorted report, make the sorting step explicit. If you need repeated priority operations, keep the heap and avoid treating its storage order as meaningful. Sorting a snapshot costs extra work; it is not a free view of the heap.

Replacing an extreme is a distinct operation

import HeapModule

var scores = Heap([10, 30, 20])
print("old min:", scores.replaceMin(with: 25))
print("new min:", scores.min ?? -1)
print("new max:", scores.max ?? -1)
print("old max:", scores.replaceMax(with: 15))
print("final min:", scores.min ?? -1)
print("final max:", scores.max ?? -1)
old min: 10
new min: 20
new max: 30
old max: 30
final min: 15
final max: 25

Replacing 10 with 25 leaves 20 as the minimum and 30 as the maximum. Replacing 30 with 15 then makes 15 the minimum and 25 the maximum. Both replacement methods return the displaced value and repair the heap in O(log n) comparisons.

These operations require a nonempty heap. They are not interchangeable with an insertion followed by an arbitrary deletion: the API specifically replaces one selected extreme. That can express a bounded selection algorithm clearly, but callers must decide whether dropping the current minimum or maximum matches their application rule.

Where the two-ended queue fits

A bounded top-score set

Suppose a tool keeps the three highest scores seen so far. It can hold three values, inspect the smallest retained score, and replace that minimum only when a better candidate arrives. The replacement operation in the previous section demonstrates the underlying step. A real implementation must also define how to handle fewer than three values and ties. A min-heap alone could solve this particular one-ended problem; the second extreme is not required.

A simulation’s pending events

A simulation can store comparable event times and pop the earliest time with popMin(). During inspection, max also reveals the latest scheduled time without scanning all events. This is a good fit only if events are ordered by the same comparable value and the application does not need stable ordering for equal timestamps. For equal-time events, include an explicit tie-breaker in the comparable event model.

Monitoring a bounded range

An in-memory monitoring tool can track the smallest and largest pending readings as it inserts or removes them. Both extremes are immediately available, but Heap does not provide efficient lookup or deletion of an arbitrary reading by identity. If the application mostly needs random access, searching, or sorted traversal, a different container may be simpler.

Version, compatibility, and the useful limit

The inspected implementation and tests are from the 1.2.1 tag of apple/swift-collections. Its package manifest declares Swift tools 5.10 and exports HeapModule. The source headers identify the project license as Apache-2.0 with the Swift runtime library exception. The current default branch has changed since that tag, so the article intentionally pins its source claims rather than treating main as a fixed version.

A heap is not a sorted array, a searchable index, or a concurrency-safe scheduler by itself. The Heap type is conditionally Sendable when its element type is Sendable; that does not make concurrent mutation of one variable safe. It also does not decide which business priority is correct: Comparable supplies that ordering.

The most useful design decision here may be the missing Sequence conformance. By refusing to promise an iteration order, the library keeps the representation free to serve the operations that matter: find and remove either extreme without sorting everything between them.

Sources
Next PostSwift Log: Why Context Metadata Belongs at the Logging Boundary