同splay tree一样,treap也是一个平衡二叉树,不过Treap会记录一个额外的数据,即优先级。Treap在以关键码构成二叉搜索树的同时,还按优先级来满足堆的性质。因而,Treap=tree+heap。这里需要注意的是,Treap并不是二叉堆,二叉堆必须是完全二叉树,而Treap可以并不一定是。