本文主要是介绍Teap树堆，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
Treap
http://hihocoder.com/problemset/problem/1325
树堆，是二叉搜索树和堆的结合，是为了平衡二叉搜索树，使得平均复杂度为O(logn)。通过随机数来用堆的性质调整树结构。
左旋
右旋
#include<cstdio>
#include<cmath>
#include<cstdlib>using namespace std;struct _node
{struct _node * left;struct _node * right;int key;int priority;_node(int k):left(NULL), right(NULL), key(k), priority(rand()){};
};//左旋
void leftRotate(struct _node *& a)
{struct _node * b = a->right;a->right = b->left;b->left = a;a = b;
}//右旋
void rightRotate(struct _node *& a)
{struct _node * b = a->left;a->left = b->right;b->right = a;a = b;
}//插入
void insert(struct _node *& root, int key)
{if(!root){root = new _node(key);return;}if(key < root->key){insert(root->left, key);if(root->priority > root->left->priority)rightRotate(root);}else{insert(root->right, key);if(root->priority > root->right->priority)leftRotate(root);}
}//查询
int query(struct _node * root, int key)
{struct _node * p = root;int res = 0;while(p){if(p->key == key) return key;else if(p->key < key){res = p->key;p = p->right;}elsep = p->left;}return res;
}int main(void)
{int n,c,k;scanf("%d",&n);struct _node * root = NULL;while(n--){scanf("%c%c%d", &c,&c,&k);if(c == 'I')insert(root, k);elseprintf("%d\n", query(root, k));}return 0;
}
这篇关于Teap树堆的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
