This seems to me like useful functionality to add. @timv pointed out that it's worth adding a replaceMin (and replaceMax) because they can be implemented more efficiently than a removeMin followed by an insert.
I imagine a good way to mutate an item or its priority might be to add Collection conformance so the Index can be used to identify it in constant time.
I think this could make sense. [<item>: <priority>] for some reason feels a little weird to me. Maybe we should flip them or maybe I'd get used to it?
I think you would get used to it. It would be weird with priority first unless the items were sorted, it would look very strange I think?
With regard to updating priorities - do anyone actually have any practical use cases where they’ve done that? (I don’t, so just curious so we don’t spend additional time on features which no one wants?)
I like the use of min-max heap in this implementation.
I think it's repetitive, and somewhat counter-productive, to have both the pop and remove functions. They differ only in the optional-ness of their return value, but their names don't give any hint to it. I think it takes more mental space to remember which set returns optional value and which doesn't, and makes it harder to read code that uses both. I would prefer to have only 1 set of functions that returns only optional values, and force-unwrap them if I'm sure they're not nil. Since both sets of functions do the same thing, it makes the coder author's intention clearer if we keep with just one set of them.
Additionally, I think they should be annotated with @descardableResult, to be consistent with standard library's remove functions.
@discardableResult
public mutating func removeMin() -> Element?
@discardableResult
public mutating func removeMax() -> Element?
I'm not sure if I should comment on _bubble functions here since they're underscored and not covered int the overview of APIs, but I think their argument label should be elementAt instead of startingAt.
This is consistent with standard library types, and I see no good reason to deviate here.
It would not be consistent to adopt your suggestion and have remove* return an optional result, as that's not what the standard library remove* functions do but rather what the pop* functions do.
They used to be recursive, so startingAt made more sense than elementAt. Now that they're iterative, we should probably change the labels as you suggest.
OK, we've decided to split PriorityQueue<Element: Comparable> into Heap<Element: Comparable> (a min-max heap implementation) and PriorityQueue<Value, Priority: Comparable>, with the latter being a lightweight wrapper around the former.
If interested, the Heap PR is up for review. Once that has landed, I'll update the original PR with the PriorityQueue implementation.
One thing we generally prefer doing is storing the "keys" (i.e., priority values) and the values in separate buffers, rather than in a single buffer containing key-value pairs. (This saves some memory if the two types have different alignments.) Implementing this would need a little more than just a lightweight wrapper type, though, and I'm not entirely sure if the runtime costs would outweigh the size benefits in practice.
With all the due respect to the authors of Collections package (my expertise is way less than theirs), here are a couple of packages I made that might be interesting in these regards:
Hey everyone! I'm still looking for feedback on the PR.
Particularly: as it's currently implemented, PriorityQueueuses a UInt64 to keep track of insertion order of elements (to ensure FIFO ordering for equal-priority elements). Is that overkill? Is there a better approach to ensure FIFO ordering? One potential option I've thought about is using a smaller type and resetting the counter to 0 when the queue becomes empty. Splitting the priorities and elements into two containers as @lorentey mentioned above might also solve this.
I've only skimmed so apologies if I'm missing something, but my concern here is a familiar one to anyone who remembers the RangeSet process: rather than following generic programming principles and exposing the fundamental algorithms as building blocks, the API attempts to expose one completely sealed component. It's not uncommon to start with an arbitrary (unsorted) random access collection, then heapify it and proceed with heap operations on it, without creating new storage. That's why having the heap algorithms exposed on arbitrary random access collections is useful in STL. There might be a compromise for Swift that simply exposes an init() taking an array (or you could use _copyToContiguousArray() internally on the existing init—but you should document that a copy of storage can be avoided in that case). The fully-general wrapped solution would require parameterizing PriorityQueue on the underlying storage type, so you could use a Deque, for example.
I’d like to rethink about the idea of struct Prioritized<Content>. IMO strongly tying the content with priority will give far more flexibility and better performance.
One prior concern is that PriorityQueue<Prioritized<String>> will have an award interface like queue.insert(.init("Hello", priority: 1)). There is exactly a pitch that can solve such syntax:
The @expanded mark will automatically imply .init() in function parameters, giving a cleaner expression of queue.insert("Hello", priority: 1), which is exactly the same as the current one.
One big improvement is, when sometimes the content itself can imply its priority we can now have:
enum Task: Int, PriorityProtocol {
case pending = 0
case simple
case urgent
let priority: Int { self.rawValue }
}
var queue = PriorityQueue<Task>()
queue.insert(.urgent)
queue.insert(.pending)
queue.removeMax() // Task.urgent
The interface should get cleaner and have better robustness.