[Treap] Fast random insertions collection

[alexdremov]

At this moment, no collection can address random insertions. I have a data structure implemented through implicit Treap that behaves like a general array but can do random insertions/deletions/access with O(log n).

If such a container is needed, I can open a PR. What do you think?

[alexdremov]

At the meantime, here is the comparison. The better performance is noticeable at n ~ 10^4

[alexdremov]

Opened a topic on the forum: https://forums.swift.org/t/treap-fast-random-insertions-deletions-collection/53468

[alexdremov]

As it seems like it is not really needed in swift-collections, I've created a package that has more efficient implementation. Also, I benchmarked the solution and created comparison graphs.

AlexRoar/TreeArray

Preview:

Random insertions

Random removals

Prepend

Remove first