查找
和一般的二叉搜索树一样,但是由于Treap的随机化结构,Treap中查找的期望复杂度是O(logn)。...但 Splay 在查找时也会调整结构,这使得 Splay 灵活性稍有欠缺。
Splay 的查找插入删除等基本操作的时间复杂度为均摊O(logN)而非期望。...为了查找快速,可以用Trie树。之后我们建立一个双关键字的Treap,关键字1为得分从小到大,关键字2为时间戳从大到小,这种排列方式的逆序,恰好是我们要的顺序(也可以直接就是逆序)。...但是如果我们要求一种 “双端优先队列”,即要求同时支持插入、取出最大值、取出最小值的操作,用一个单纯的堆就不能高效地实现了。
(可以用两个堆来实现,两堆中的元素都互指,但维护两个堆比较复杂。)...我们可以方便地使用Treap实现双端优先队列,只需建立一个 Treap,分别写出取最大值和最小值的功能代码就可以了, 无需做任何修改。由于Treap平衡性不如堆完美,但期望时间仍是 O(logN)。