Treap（树堆）：一种随机化平衡二叉搜索树数据结构，把二叉搜索树（BST）的“按键有序性”和堆（Heap）的“按优先级堆序性”结合在一起。每个节点通常有两项：key 用于满足 BST 的中序有序，priority（常随机生成） 用于满足堆性质，从而在期望意义上保持较好的平衡与操作效率（如查找、插入、删除多为期望 (O(\log n))）。
/triːp/
I stored the IDs in a treap for fast lookups.
我把这些 ID 存在 treap（树堆）里，便于快速查询。
By assigning each node a random priority, the treap stays balanced in expectation, so inserts and deletes remain efficient even as the dataset grows.
通过给每个节点分配随机优先级，treap 在期望意义上保持平衡，因此即使数据量增长，插入和删除通常仍然高效。
Treap 是由 tree（树） + heap（堆） 拼合而成的混成词（portmanteau），强调它同时具备“像树一样按 key 有序”和“像堆一样按 priority 维护结构”的双重特性。该结构常与“随机化搜索树”思想一起出现。
Select Language