# \[swift-collections 1.1\] Heap API RFC

**URL:** <https://forums.swift.org/t/swift-collections-1-1-heap-api-rfc/68447>\
**Category:** Collections\
**Created:** [November 14, 2023, 5:15am UTC](https://forums.swift.org/t/swift-collections-1-1-heap-api-rfc/68447 "2023-11-14T05:15:13Z")\
**Posts on this page:** 1\
**Showing post:** 4

<div class="post-metadata">

**Author:** ![lorentey](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/lorentey/32/1299_2.png) [@lorentey](https://forums.swift.org/u/lorentey)\
**Post date:** [November 14, 2023, 8:16am UTC](https://forums.swift.org/t/swift-collections-1-1-heap-api-rfc/68447/4 "2023-11-14T08:16:15Z")

</div>

Great questions!

> [@wadetregaskis](#):
>
> I feel like I'm missing something, regarding all this and particularly what leads to the concluding sentence. It seems to be saying that instead of e.g. putting `String`s in a `Heap`, it's expected that most uses will have some custom wrapper around `String` instead?

No — if you want a heap of `String`s, and you’re happy with `String`’s ordering, then `Heap<String>` is perfect. All I’m saying is that it’s no big deal if you want your heap to use a different order.

If you need a custom ordering relation, then you’ll simply need to wrap your strings in some custom type of your own. (This is not a design defect, but it’s very much by design. Defining new types is easy.)

> [@wadetregaskis](#):
>
> This seems related to Swift's general choice to eschew collection-instance-specific customisation of equality / hashing / comparison. As opposed to e.g. C++ where STL (and Boost etc) collection types are typically parameterised (via the generics system) for these factors.

Yes, this is directly following a clear, strong pattern established by the Swift Standard Library. `Set` is a collection of `Hashable` elements, not a collection of arbitrary elements with a separate type parameter that describes how to compare and hash them.

As I noted in point (7), Swift does not make it possible to supply default values for generic type arguments, so trying to do C++-style mix-in parameters would make the API unpalatable for the common case.

> [@wadetregaskis](#):
>
> Even in Swift there are exceptions to this apparent rule, e.g. the standard `sort` et al methods take an optional comparison closure.
> 
> So hopefully this isn't too tangential or generic (vs `Heap`), but even knowing Swift's patterns it's not apparent to my _why_ new collections should be implemented this way.

The crucial distinction is that `sort` et al. are generic _functions_, not generic _types_. A type whose values can get passed around in between modules of an app generally needs to guarantee a particular behavior for itself, so that code can usefully interact with it.

All code that encounters a `Set<String>` needs to agree on how `==` and `hash(into:)` get implemented.

All code that deals with `SortedSet<String>` values need to agree on how the `==`/`<` relations work.

All code that receives a `Heap<String>` is guaranteed that the minimum and maximum items will be the ones that correspond to the `<` relation.

Swift is a strongly typed language. We like Swift's rich type system, and we want to make the best use of it.

This topic has been extensively covered in previous discussions, [some of them directly involving Heap](https://forums.swift.org/t/what-is-intended-for-using-heap-with-non-comparable-values/62032). (Beware, the linked discussion ended quite rudely.)

> [@wadetregaskis](#):
>
> Plenty of `Collection`- and `Sequence`-conforming types have undefined orders of iteration, e.g. `Dictionary` ("_The order of key-value pairs in a dictionary is stable between mutations but is otherwise unpredictable._").

`Set` and `Dictionary` directly conforming to Sequence is an API design regret. If we were starting from scratch, I’d probably push for moving these conformances into a separate view, just like with `Heap`. (Suggesting such a move may have been possible in Swift 1 era. I don’t think it would be practical today.)

> [@wadetregaskis](#):
>
> It'd be one thing if `unordered` were an actual view that might have a different presentation to the base type, e.g. `String`'s `unicodeScalars`, but it sounds like it's nothing more than the actual internal storage?

Like [`OrderedSet`'s `elements` view](https://swiftpackageindex.com/apple/swift-collections/1.0.5/documentation/orderedcollections/orderedset/elements), `Heap`'s `unordered` view simply directly exposes the underlying `Array` instance. This does not in any way lessen its view-ness -- it is still a bona fide, card carrying, actual view!

A view simply provides an alternate way of looking at the underlying representation, different from the default one.

The name `unordered` comes from [`OrderedSet`'s `unordered` view](https://swiftpackageindex.com/apple/swift-collections/1.0.5/documentation/orderedcollections/orderedset/unordered), where it is used to provide a `SetAlgebra` conformance. (As `SetAlgebra`'s expectation for equality is incompatible with `OrderedSet`'s order-sensitive equivalence relation.)

`Heap`'s `unordered` view fulfills an analogue role for `Sequence`/`Collection` as `OrderedSet`'s `unordered` view did for `SetAlgebra`.

(Note: [`TreeSet` and `TreeDictionary`](https://forums.swift.org/t/api-review-for-1-1-hash-array-mapped-prefix-trees/61151) did not relegate their `Sequence` conformances to a separate view, as they are designed to be drop-in replacements of `Set` and `Dictionary` -- they needed to faithfully emulate their API surface, wrinkles and all.)

> [@wadetregaskis](#):
>
> That seems _less_ flexible for the future, since it's explicitly stating that `unordered` is an `Array<Element>` - and therefore making it a potentially expensive operation if the underlying storage is one day made something else - whereas if `Heap` were simply a `Collection` itself it could abstract away any connection to the internal storage.

Min-max heaps are, by definition, represented by an implicit tree stored in an array. Having to expose this storage is not going to ever become a limitation.

(Note: We are not trying to pretend that it would be practical for `Heap` to switch to some radically different implementation, such as Fibonacci heaps. If we want to implement a different data structure, then we'd do it by defining a different type.)

If we ever want to generalize `Heap` to support storage types other than `Array`, then we will be able to do so by doing that in a separate type, as explained in point (7).

As [has been very clearly noted](https://forums.swift.org/t/api-review-priorityqueue-apis/49932/53), we sometimes want to form a heap in place using some pre-existing storage -- and this initial form of `Heap` intentionally does not allow that.

This is similar to how we decided that `OrderedSet` would hardwire `Array` as its underlying storage -- just like with `Heap`, it would sometimes be useful to be able to define, say, a uniquing `Deque`, and the current `OrderedSet` does not allow that.

(For what it's worth, in the three years `OrderedSet` has been in use, I have seen zero requests for generalizing it -- even though a Deque-based OrderedSet would allow allow efficient insertions/removals at its start, not just at its end.

That said, I think `Heap` is a bit more likely to receive such requests, so I expect we'll eventually end up doing this -- but probably not before we have non-copyable sequence/collection protocols. Most heap operations are implemented on the core [`Heap._UnsafeHandle`](https://github.com/apple/swift-collections/blob/main/Sources/HeapModule/Heap%2BUnsafeHandle.swift) type, which is an UnsafeBufferPointer-like construct, abstracting away the minutiae of Array access. One way to reformulate this in a safer way would be to use something like a non-copyable [BufferView](https://forums.swift.org/t/roadmap-language-support-for-bufferview/66211) -- this would let us define a fixed-size, backing-store agnostic contiguous heap type as a public replacement of `Heap._UnsafeHandle`, and then use it in all sorts of generalizations of `Heap`.

I don't think any of these future directions need to hold up the release of `Heap` in the source-stable (but not ABI-stable!) swift-collections package.

---

_[View the full topic](https://forums.swift.org/t/swift-collections-1-1-heap-api-rfc/68447)._
