-
-
-
-
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)。
*/ -
如何改变自己的先天性格
-
-
-
高级微观经济学的逻辑
-
R 语言的tidyverse
-
garvey说:
rust 语言的优势
Rust 语言有着许多优势，比如：
-
Rust 语言是安全的： Rust 具有强大的安全性和可靠性，它采用了静态类型系统，可以检测出大部分常见的安全漏洞，可以有效防止缓冲区溢出，内存泄漏等安全漏洞。
-
Rust 语言是快速的： Rust 语言是一种非常快速的编程语言，它比 C 语言更快，它具有非常强大的性能优化能力，可以大大降低 CPU 占用率。
-
Rust 语言拥有丰富的功能： Rust 语言拥有大量的功能，可以支持多核处理，支持并发处理，支持内存管理，支持函数式编程，支持垃圾回收等等。
-
Rust 语言的可移植性： Rust 语言拥有良好的可移植性，可以轻松地在多种平台上运行，比如 Windows、Linux、macOS 等等。
-
Rust 语言的可读性： Rust 语言有着清晰的语法，可读性极高，易于学习和维护，适合用于大型项目。
-
