Heap.Tail slow

[simendsjo]

I notice Heap.Tail does a lot of work. The documentation says insert adds items in sorted order, so I would assume Tail should be fast. The following shows 100_000 calls to uncons.

Looks like it will take some time to learn the implementation enough to speed it up, but I'll take a stab if no one want to look at it.

[github-actions]

🤖 This is an automated response from Repo Assist.

The slowness is rooted in how ofSeq constructs the heap and how Tail (delete-min) works in a pairing heap.

How ofSeq builds the heap

Rather than using the standard pairing heap insert, ofSeq folds over the sequence doing sorted merges. For a descending sequence this produces a root node with all n−1 elements as direct children:

T(max, [child₁; child₂; … childₙ₋₁])

How Tail works on that structure

Tail (delete-min) must merge all of the root's children back into a single heap. The implementation does a two-pass left-to-right pairing merge (combinePairs + List.fold mergeData), which on that degenerate structure is O(n) for the first call. Subsequent calls on the now-balanced heap are O(log n) amortized — so repeated uncons on a heap built with ofSeq pays O(n) up-front.

Possible improvements

1. Build with Insert instead of ofSeq — each Insert is O(1) (single merge with root) and yields a structure where Tail is O(log n) amortized from the start.
2. Right-to-left second pass in Tail — standard pairing heap analysis gives better constants when the second merging pass goes right-to-left (i.e., List.foldBack mergeData list E instead of List.fold mergeData E). The current left fold is correct but may produce deeper trees.
3. Alternative structures — LeftistHeap and BinomialHeap in the Experimental namespace have stricter O(log n) worst-case (not just amortized) guarantees for delete-min.

Happy to review a PR if someone wants to try fix 2 above — it's a small change with a measurable effect on worst-case behaviour.

Generated by Repo Assist · ◷

To install this agentic workflow, run

gh aw add githubnext/agentics/workflows/repo-assist.md@30f2254f2a7a944da1224df45d181a3f8faefd0d