y                     x
      / \                   / \
     x   T3   右旋→        T1  y
    / \                       / \
   T1 T2                     T2 T3

        (D,9)
       /     \
    (B,7)   (F,8)
    /   \    /   \
 (A,4) (C,5)(E,2)(G,3)

#include <iostream>
#include <cstdlib>   // for rand, srand
#include <ctime>     // for time
using namespace std;

// 树堆节点结构
struct TreapNode {
    int key;                // 键值（用于BST排序）
    int priority;           // 优先级（随机生成，用于堆排序）
    TreapNode* left;        // 左孩子指针
    TreapNode* right;       // 右孩子指针

    // 构造函数：创建新节点，自动生成随机优先级（0~99）
    TreapNode(int k) : key(k), left(nullptr), right(nullptr) {
        priority = rand() % 100;
    }
};

// 右旋：以y为轴，将它的左孩子x旋上去，返回新的根
TreapNode* rightRotate(TreapNode* y) {
    TreapNode* x = y->left;          // 左孩子
    TreapNode* T2 = x->right;        // 左孩子的右子树

    // 旋转
    x->right = y;
    y->left = T2;

    return x; // 新根是x
}

// 左旋：以x为轴，将它的右孩子y旋上去，返回新的根
TreapNode* leftRotate(TreapNode* x) {
    TreapNode* y = x->right;         // 右孩子
    TreapNode* T2 = y->left;         // 右孩子的左子树

    // 旋转
    y->left = x;
    x->right = T2;

    return y;
}

// 插入节点（递归方式）
TreapNode* insert(TreapNode* root, int key) {
    // 1. 如果树为空，直接创建新节点返回
    if (root == nullptr) return new TreapNode(key);

    // 2. 根据BST性质决定插入左子树还是右子树
    if (key < root->key) {
        root->left = insert(root->left, key);
        // 3. 插入后检查：如果左孩子的优先级大于根，需要右旋
        if (root->left && root->left->priority > root->priority)
            root = rightRotate(root);
    } else if (key > root->key) {
        root->right = insert(root->right, key);
        // 如果右孩子的优先级大于根，需要左旋
        if (root->right && root->right->priority > root->priority)
            root = leftRotate(root);
    }
    // 若键值相等，不处理（本实现不插入重复键）
    return root;
}

// 删除节点（递归方式）
TreapNode* erase(TreapNode* root, int key) {
    if (root == nullptr) return nullptr;

    // 先在子树中查找
    if (key < root->key) {
        root->left = erase(root->left, key);
    } else if (key > root->key) {
        root->right = erase(root->right, key);
    } else {
        // 找到要删除的节点
        // 情况1：左右孩子都为空，直接删除
        if (root->left == nullptr && root->right == nullptr) {
            delete root;
            return nullptr;
        }
        // 情况2：只有一个孩子或两个孩子
        // 选择优先级较大的孩子旋转上去（如果某个孩子为空，则另一个孩子优先级视为无限大）
        // 注意：这里先判断左孩子为空，或右孩子优先级大于左孩子，则左旋
        if (root->left == nullptr || (root->right && root->right->priority > root->left->priority)) {
            // 左旋后原来的root变为左孩子
            root = leftRotate(root);
            // 现在要删除的节点（原root）跑到左子树，递归删除
            root->left = erase(root->left, key);
        } else {
            // 否则右旋
            root = rightRotate(root);
            // 要删除的节点跑到右子树
            root->right = erase(root->right, key);
        }
    }
    return root;
}

// 中序遍历，输出 (键值,优先级) 序列
void inorder(TreapNode* root) {
    if (root == nullptr) return;
    inorder(root->left);
    cout << "(" << root->key << ", " << root->priority << ") ";
    inorder(root->right);
}

int main() {
    srand(time(nullptr)); // 用当前时间初始化随机种子

    TreapNode* root = nullptr;
    // 插入一些键值（可以是学号、分数等）
    int keys[] = {5, 3, 7, 2, 4, 6, 8};
    for (int key : keys) {
        root = insert(root, key);
    }
    cout << "中序遍历（键值,优先级）: ";
    inorder(root);
    cout << endl;

    // 删除键值5
    root = erase(root, 5);
    cout << "删除5后: ";
    inorder(root);
    cout << endl;

    // 再插入重复键看看（不会插入）
    root = insert(root, 5);
    cout << "重新插入5后: ";
    inorder(root);
    cout << endl;

    return 0;
}

import random
random.seed()  # 初始化随机种子（通常自动根据时间初始化）

class TreapNode:
    def __init__(self, key):
        self.key = key          # 键值
        self.priority = random.randint(0, 99)  # 随机优先级
        self.left = None        # 左孩子
        self.right = None       # 右孩子

def right_rotate(y):
    """右旋，返回新的根"""
    x = y.left
    T2 = x.right
    x.right = y
    y.left = T2
    return x

def left_rotate(x):
    """左旋，返回新的根"""
    y = x.right
    T2 = y.left
    y.left = x
    x.right = T2
    return y

def insert(root, key):
    """递归插入，返回新的根"""
    if root is None:
        return TreapNode(key)

    if key < root.key:
        root.left = insert(root.left, key)
        if root.left.priority > root.priority:
            root = right_rotate(root)
    elif key > root.key:
        root.right = insert(root.right, key)
        if root.right.priority > root.priority:
            root = left_rotate(root)
    # 键相等时不做插入
    return root

def erase(root, key):
    """递归删除，返回新的根"""
    if root is None:
        return None

    if key < root.key:
        root.left = erase(root.left, key)
    elif key > root.key:
        root.right = erase(root.right, key)
    else:
        # 找到要删除的节点
        if root.left is None and root.right is None:
            return None
        # 选择优先级较大的孩子旋转上来
        if root.left is None or (root.right and root.right.priority > root.left.priority):
            root = left_rotate(root)   # 左旋后原来的root变为左孩子
            root.left = erase(root.left, key)
        else:
            root = right_rotate(root)
            root.right = erase(root.right, key)
    return root

def inorder(root):
    """中序遍历，打印节点信息"""
    if root:
        inorder(root.left)
        print(f"({root.key},{root.priority})", end=" ")
        inorder(root.right)

# 测试
if __name__ == "__main__":
    root = None
    for key in [5, 3, 7, 2, 4, 6, 8]:
        root = insert(root, key)
    print("中序遍历:", end=" ")
    inorder(root)
    print()

    root = erase(root, 5)
    print("删除5后:", end=" ")
    inorder(root)
    print()

    root = insert(root, 5)  # 尝试重复插入，不会生效
    print("重复插入5后:", end=" ")
    inorder(root)
    print()