Including a mergeable heap type?

[saolof]

Inspired by reading the excellent comparison of heap types by Larkin, Sen, and Tarjan over at https://arxiv.org/pdf/1403.0252.pdf - the quick summary of the paper is that contrary to popular belief, there are apparently quite a few workloads where pointer-based heaps can significantly outperform implicit d-ary heaps implemented on arrays. Apparently, the performance of one type vs the other is heavily workload-dependent even if merges are not used, and even the "known to be slow" heap types like Fibonacci heaps turned out to have their slowness largely exaggerated, being much faster than a sorted tree used as a priority queue for example.

Since pointer based heaps can also support O(1) or O(log(N)) merges, this does make me think about whether or not DataStructures.jl should provide a mergeable heap type that supports fast merges, in order to be complementary to the more common fully-implicit binary heap types?

I wrote my own quick version of pairing heaps in Julia, but the performance for a heap type based on mutable structs seems fairly poor and it can probably be improved on quite a bit: https://gist.github.com/saolof/1e8e0f062894c4b59ccb06f8005ac8d7 . That version also does not have parent pointers, but adding parent pointers could speed up some operations and enable a decrease_key operation with excellent asymptotic performance. The (strict) immutable & persistent version that I wrote outperformed my expectations (being roughly four times faster on a heapsort workload) and I'm currently using it in a personal project that uses heap merges extensively, and it may be worth including in FunctionalCollections.jl or its own package. With that said, LST did their comparison in C, so there may be some performance differences due to the differences in memory models with Julia's generational GC. Semi-implicit versions of the d-ary heap (similar to the unrolled linked lists used for the Deque type, with the nodes at the lowest level of a block having children) could also be worth considering, since they should be mergeable in O(log(n)) as well.