Rust is missing an advanced heap

[Gankra]

One that lets you modify the priority of keys.

My academic background tells me that a pairing_heap is excellent, but I've also heard good things of a meldable heap?

• https://en.wikipedia.org/wiki/Pairing_heap
• https://en.wikipedia.org/wiki/Randomized_meldable_heap

Of note is a nasty API issue around how you specify that a key is to be reprioritized.

My intuition is that push returns a token, and then you increase_key(&token, new_weight) or whatever. The token is a pointer to the node that contains the element, but this has a fundamental memory safety issue (the element associated with the token may have been popped).

One solution is to just make decrease/increase unsafe.

The other is to use Rcs internally, and have tokens be a Weak.

Neither is super great, honestly.

[Gankra]

Note that I posit this is impossible to overcome. This is a fundamental issue of data trust, and no mechanism I am aware of could possibly prevent having to validate the tokens (and in turn, maintaining metadata to make it possible to validate the tokens).

Perhaps there's a fundamentally different approach, though?

The pairing heap could have an intrusive map, so you just do lookup with actual keys, but this is definitely way more overhead than necessary.

Note that this kind of heap is generally an optimization to begin with, so too much overhead negates even using it.

[ssylvan]

I think a way of handling this is to allocate the elements of the queue "manually" by just storing them in a big vec, and refer to them using indices internally. The elements are allocated in a big vec (which can grow dynamically, indices remain valid!). Each "slot" of this array also has a u64 "version number". Whenever an element is popped, the slot in the big array is cleared, and the corresponding version number is incremented. Tokens contain an index to a slot in the element array, as well as the current version number. decrease_key can thus fail, if the token refers to un "unallocated" element in the array, or if the version number isn't correct.

Note that this is essentially just implementing manual memory control over an array and using indices, but the upside is that it needs no unsafe code an won't corrupt the global program heap or the runtime or anything. At worst the data structure fails. But yes, this does mean runtime validation of tokens.

[FranklinChen]

What are the required complexities of the desired operations? In the persistent data structure world, I use a priority search queue when needing to modify priorities, but that not may be best for Rust.

[pythonesque]

It seems like this is a good use case for just making the data structure intrusive (as opposed to storing extra intrusive metadata). Then removal from the structure doesn't actually free the associated memory.

[constinit]

Would a BTreeMap work here? You get logarithmic insert, delete, update, and find_min. It's also cache friendly.

It would be nice to see a comparison of heap performance on modern hardware, but I'm having trouble finding one.

[FranklinChen]

For reference, the persistent tree-based priority search queue:

• insert is log
• delete is log
• modify is log
• adjust priority is log
• lookup is log
• find min priority is constant
• delete min priority is log
• build is linear

[Gankra]

Algorithmic complexity is notably total nonsense for high-performance heaps.

A fibonacci is the theoretical best heap: https://en.wikipedia.org/wiki/Fibonacci_heap

Find-minimum is O(1) amortized time.[1] Operations insert, decrease key, and merge (union) work in constant amortized time.[2] Operations delete and delete minimum work in O(log n) amortized time.[2] This means that starting from an empty data structure, any sequence of a operations from the first group and b operations from the second group would take O(a + b log n) time. In a binomial heap such a sequence of operations would take O((a + b) log n) time. A Fibonacci heap is thus better than a binomial heap when b is asymptotically smaller than a.

A pairing heap meanwhile both has non-tight bounds, and the lower bounds it does have make it theoretically worse than a fibonacci heap. However in practice the hidden constants on a fibonacci heap are attrocious, and a pairing heap is supposed to be better.

[Gankra]

So mostly I care about actual perf. a simple benchmark would be "do dijkstras as fast as possible".

[FranklinChen]

Yes, I only care about actual performance also. Ironically, I just tweeted today on the pointlessness of FIbonacci heaps :-) https://twitter.com/franklinchen/status/644894021144461312

[ssylvan]

IME a D-ary heap organized as a complete D-ary tree encoded in an array (implemented like a binary heap, but with better cache locality.. so child pointers are implicit etc.) beats all of the fancy heaps in practice. Benchmark to find the best D (possibly depends on element size).

It doesn't have the best time complexity for many operations, but the constant factors are pretty minimal so you'd have to be doing something pretty out of the ordinary for it to be beaten by more complex option.

[Gankra]

@ssylvan How does one provide decrease_key that isn't O(n) (literally a linear search for the element) for such a data structure?

[llogiq]

Perhaps unrelated, but I have a binary heap implementation in Java (unfortunately belonging to my employer, so I can't show code) that allows to change the first element without allocation, re-shuffling the heap as necessary (I use this for a fast "first N out of X" where X ≫ N. It uses a bounded array for data storage.

This interface could be made quite elegant in rust, e.g. fn poke<F, T, U>(self, f: F) -> Option<U> where F: FnOnce(&mut T) -> U. This nicely complements peek, so there are no problems with reordering.

[ssylvan]

@gankro Reduce priority value, then swap with parent if necessary to maintain heap invariant (repeat until you're at root, or the element is in the right place). That's O(log_d n), where d is the branching factor (i.e. higher branching factor means you don't need to do a lot of work for even huge heaps.. e.g. a billion elements for d=8 is only 10 levels deep).

[llogiq]

@ssylvan Note that the constant factors grow with the branching factor, also as your d approaches n, our operations become essentially linear.

[Gankra]

@ssylvan I don't understand how you're finding the element. External users of the data structure can't just have pointers/indices, because those are constantly shifting without a node-based structure.