Zip tree

[1] Zip trees are similar to max treaps except ranks are generated through a geometric distribution and maintain their max-heap property during insertions and deletions through unzipping and zipping rather than tree rotations.

The tree is max heap ordered with respect to the ranks with ties broken in favor of smaller keys.

The time it takes to unzip or zip is proportional to one plus the number of nodes on the path(s) being unzipped/zipped.

[1] When inserting a node x into a zip tree, first generate a new rank from a geometric distribution with a probability of success of 1/2.

While creating this path top-down, nodes are added as left and right children of their parent accordingly based on their keys.