树堆的基本概念
树堆（Treap）是二叉排序树（Binary Sort Tree）与堆（Heap）结合产生的一种拥有堆性质的二叉排序树。
但是这里要注意两点，第一点是Treap和二叉堆有一点不同，就是二叉堆必须是完全二叉树，而Treap并不一定是；第二点是Treap并不严格满足平衡二叉排序树（AVL树）的要求，即树堆中每个节点的左右子树高度之差的绝对值可能会超过1，只是近似满足平衡二叉排序树的性质。
Treap每个节点记录两个数据，一个是键值，一个是随机附加的优先级，Treap在以关键码构成二叉排序树的同时，又以结点优先级形成最大堆和最小堆。所以Treap必须满足这两个性质，一是二叉排序树的性质，二是堆的性质。如下图，即为一个树堆。
关键步骤
查找
按照正常BST的查找过程即可
插入
- 给新节点一个随机的权重值，按照普通二叉搜索树，使用key进行插入
- 为了保证堆的特性，插入完成后要进行旋转操作，保证仍为最大堆或最小堆。以最大堆为例，若插入到右子树，且权重比父结点大，就要实现一次左旋转，使右子树根结点成为新的父节点；反之左旋，直到满足堆的特性为止
删除
- 按照正常的查找流程找到待删除节点后，有三种情况
- 待删除结点本身就是叶子结点，直接删除即可
- 待删除结点只有一个孩子（一棵子树），用这个孩子替换待删除结点，实现删除效果
- 待删除结点两棵子树均不为空时，先进行旋转。以最大堆为例，找到权重更大的孩子，向相反方向旋转（即若左孩子权重更大，执行右旋），直到待删除结点满足上面两种情况之一，再进行删除
具体实现
参考LeetCode(cn) 第1438题的实现，其中对于旋转的优雅实现值得一学
import "math/rand"
type node struct {
ch [2]*node
priority int
key int
cnt int
}
func (o *node) cmp(b int) int {
switch {
case b < o.key:
return 0
case b > o.key:
return 1
default:
return -1
}
}
func (o *node) rotate(d int) *node {
x := o.ch[d^1]
o.ch[d^1] = x.ch[d]
x.ch[d] = o
return x
}
type treap struct {
root *node
}
func (t *treap) ins(o *node, key int) *node {
if o == nil {
return &node{priority: rand.Int(), key: key, cnt: 1}
}
if d := o.cmp(key); d >= 0 {
o.ch[d] = t.ins(o.ch[d], key)
if o.ch[d].priority > o.priority {
o = o.rotate(d ^ 1)
}
} else {
o.cnt++
}
return o
}
func (t *treap) del(o *node, key int) *node {
if o == nil {
return nil
}
if d := o.cmp(key); d >= 0 {
o.ch[d] = t.del(o.ch[d], key)
} else {
if o.cnt > 1 {
o.cnt--
} else {
if o.ch[1] == nil {
return o.ch[0]
}
if o.ch[0] == nil {
return o.ch[1]
}
d = 0
if o.ch[0].priority > o.ch[1].priority {
d = 1
}
o = o.rotate(d)
o.ch[d] = t.del(o.ch[d], key)
}
}
return o
}
func (t *treap) insert(key int) {
t.root = t.ins(t.root, key)
}
func (t *treap) delete(key int) {
t.root = t.del(t.root, key)
}
func (t *treap) min() (min *node) {
for o := t.root; o != nil; o = o.ch[0] {
min = o
}
return
}
func (t *treap) max() (max *node) {
for o := t.root; o != nil; o = o.ch[1] {
max = o
}
return
}
func longestSubarray(nums []int, limit int) (ans int) {
t := &treap{}
left := 0
for right, v := range nums {
t.insert(v)
for t.max().key-t.min().key > limit {
t.delete(nums[left])
left++
}
ans = max(ans, right-left+1)
}
return
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
参考
树堆（Treap）图文详解与实现
leecode-cn 1438
