树堆 思想与实现

1.思想

Treap(树堆)是一种比较简单的平衡二叉树，是Tree和Heap的结合，它拥有两个属性：（键值，优先级）：

• 对于节点的键值，是一颗排序二叉树
• 对于节点的优先级，根节点最小/大

1.1 性质

Treap有如下性质

• 令每个节点的优先级互不相等，整棵树的形态是唯一的，与插入顺序无关（这个是较二叉搜索树的优点）

2.一般性描述

• 主要是较二叉搜索树多了左旋、上升的连个操作

3.实现、题目

待填

待补知识点

欧拉回路 判图+例题 动态树 Splay