-
guest说:
写一篇由于你打英雄联盟而惹女朋友生气的道歉信
亲爱的：
你好！
我知道你对我昨晚玩英雄联盟的行为很不满，我很抱歉。我知道我过去的行为很不应该，真的很抱歉。我会想办法让你开心，把这件事情放在一边，我知道这对你来说可能是一件很难的事情，但我真的很抱歉。
我承诺以后会尽量把我的注意力放在你和我们的关系上，不再让你担心我玩游戏，只是我有时候会忘记，所以你有时候会受到伤害，但是我会努力记住这一点，绝不再犯同样的错误。
我知道，我们之间的关系是非常重要的，我会更加注重这一点，努力让你满意。
最后，我只想说，我非常抱歉，我会尽力做到更好。请原谅我。
爱你，
XXX
-
guest说:
用C++写一段Treap
算法，并给出分析
#include
using namespace std;struct TreapNode
{
int key;
int priority;
TreapNode *left, *right;
TreapNode(int k, int p) : key(k), priority(p), left(NULL), right(NULL){};
};class Treap
{
private:
TreapNode *root;public:
Treap() : root(NULL){};
~Treap() {};// 将节点 t 插入到当前 Treap 中 void insert(TreapNode *t) { if (root == NULL) root = t; else { TreapNode *p = root; TreapNode *pp = root; while (p != NULL) { pp = p; if (t->key key) p = p->left; else p = p->right; } if (t->key key) pp->left = t; else pp->right = t; // 维护堆序性 while (pp != NULL && pp->priority priority) { if (t->key key) { TreapNode *tmp = pp->left; pp->left = tmp->right; tmp->right = pp; pp = tmp; } else { TreapNode *tmp = pp->right; pp->right = tmp->left; tmp->left = pp; pp = tmp; } } // 更新根节点 root = pp; } } // 遍历输出 Treap 中的节点 void show() { _show(root); }private:
void _show(TreapNode *t)
{
if (t != NULL)
{
_show(t->left);
cout key right);
}
}
};int main()
{
Treap t;
t.insert(new TreapNode(3, 15));
t.insert(new TreapNode(2, 10));
t.insert(new TreapNode(4, 6));
t.insert(new TreapNode(1, 5));
t.insert(new TreapNode(5, 20));
t.show();
return 0;
}/*
Treap 是一种结合了二叉查找树和堆的数据结构，它是一棵二叉树，每个节点都有一个优先级，根节点的优先级最高，它有如下性质：- 每个节点的键值都大于等于它的左子树中的任意节点的键值，小于等于它的右子树的任意节点的键值；
- 每个节点的优先级都大于等于它的左子树中的任意节点的优先级，小于等于它的右子树的任意节点的优先级。
上面的程序实现了 Treap 的插入操作，主要思路是：
- 先将新节点插入到二叉查找树中，使得该节点的键值满足二叉查找树的性质；
- 向上回溯，如果发现某个节点的优先级小于新插入节点的优先级，就进行旋转操作，保持堆序性。
时间复杂度分析：
插入操作的时间复杂度为 O(logn)，因为每次插入的时候，需要在二叉查找树中查找新节点的插入位置，时间复杂度为 O(logn)；向上查找时，最多只需要查找到根节点，时间复杂度也为 O(logn)。
*/
