Treap

Treap = Tree + Heap;

正如它的名字解释的那样，treap是binary  search tree与heap的混血儿。每个节点除了有element域外还有一个priority域，在保证element满足bst性质的同时，priority需要满足堆序，即父节点的priority需要小于子节点。

插入以递归的方式进行，每次从子节点的递归层次返回后检查该子节点的优先级是否满足要求，若不满足就将其旋转上移一层。

这种递归的先自顶向下再自底向上的方法很方便一些依赖于子节点的辅助域的保存，例如size（这颗子树的节点总数）。这信息可以用来进行rank（取某值当前的序数）、select（取某序数对应的值）等经常用到的操作。

程序：ural1090.cpp