[bug] Implicit treap is not randomized

[ongyiumark]

The implicit treap does not use the priority in the nodes anywhere, so it's not randomized, which results in a very unbalanced tree. We don't get the advantage of having logarithmic height, so running time is very slow.

[leloykun]

Hi @ongyiumark !

iirc, this was actually an optimization trick

The merge operation is already size-aware (i.e. we merge the smaller subtree to the larger subtree). This "guarantees" logarithmic height in the average case.

The priority is only useful on init so we could start with a log-height tree.

Homeworks:

1. Prove that this implementation "works" in the average case anyway
2. Write a test case that breaks the implementation

[ongyiumark]

Okay, we probably need to look more into this.

I tested it on a MHC problem, and it ran significantly faster when I used the priority for merging.

[leloykun]

Oooh, can you write a PR for your codes?

(btw, starting now, I'll let you merge stiff w/o tests. I trust you. Just don't break anything!)