树堆（Treap）构造算法题解

一、题目分析

本题要求根据给定的标签-优先级对构造树堆（Treap）。Treap需满足两个条件：

1. 二叉搜索树性质：节点标签满足左子树 < 根节点 < 右子树。
2. 堆性质：节点优先级满足父节点 > 子节点（最大堆）。

二、算法思路

Treap的构造可通过二叉搜索树排序 + 堆性质调整实现，具体步骤如下：

1. 标签排序
   首先根据标签对节点进行字典序排序，确保满足二叉搜索树性质。排序后，节点按标签顺序形成一条链（左子树或右子树）。

2. 堆性质调整（基于优先级的旋转）
   利用栈结构模拟堆性质的调整过程：

   • 按排序后的顺序遍历节点，维护一个栈，栈中节点按优先级递减排列。
   • 对于当前节点，若其优先级大于栈顶节点的优先级，则弹出栈顶节点作为当前节点的左子树，直到栈顶节点优先级更高或栈为空。
   • 当前节点作为栈顶节点的右子树，或成为新的根节点（栈为空时）。

三、代码实现

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <stack>
const int maxn=5e4+7;
using namespace std;
int n,ls[maxn<<1],rs[maxn<<1];
struct Node{
    char name[101];
    int priority;
    int id;
    bool operator <(const Node a) const{
        return strcmp(a.name,name)>0;
    }
}node[maxn<<1],ans[maxn<<1];
void build(){
    stack <Node> ST;
    for(int i=1;i<=n;i++){
        Node sp=node[i],sq;
        int flag=0;
        while(!ST.empty() && ST.top().priority<sp.priority){
            sq=ST.top();
            ST.pop();
            flag=1;
        }
        if(flag)
            ls[sp.id]=sq.id;
        if(!ST.empty())
            rs[ST.top().id]=sp.id;
        else
            rs[0]=sp.id;
        ST.push(sp);
    }
}
void dfs(int now){
    if(now)
        printf("(");
    if(ls[now])
        dfs(ls[now]);
    if(now)
        printf("%s/%d",ans[now].name,ans[now].priority);
    if(rs[now])
        dfs(rs[now]);
    if(now)
        printf(")");
}
int main()
{
    while(scanf("%d",&n) && n){
        for(int i=1;i<=n;i++){
            scanf(" %[a-z]/%d",node[i].name,&node[i].priority);//名字和优先级
            //网上学到的输入方法，读到a~z以外的字符就停下，注意前面一定要有空格（跟读char一样）
            strcpy(ans[i].name,node[i].name);
            ans[i].priority=node[i].priority;
            ans[i].id=node[i].id=i;
        }
        sort(node+1,node+1+n);//排序
        build();
        dfs(0);//中序遍历
        cout<<endl;
        memset(ls,0,sizeof(ls));
        memset(rs,0,sizeof(rs));
    }
    return 0;
}

四、代码解释

1. 输入处理
   使用scanf(" %[^/]/%d", name, &priority)读取标签和优先级，[^/]表示读取直到/出现，确保正确解析输入格式。

2. 标签排序
   通过sort(node + 1, node + 1 + n)对节点按标签字典序排序，使节点满足二叉搜索树的中序遍历顺序。

3. 堆性质调整

   • 利用栈维护当前路径上的节点，保证栈中节点优先级递减。
   • 对于每个节点，弹出所有优先级低于当前节点的栈顶节点，作为其左子树，当前节点作为剩余栈顶节点的右子树，或成为根节点。

4. 输出遍历
   通过深度优先搜索（DFS）递归构建树的字符串表示，左子树、当前节点、右子树依次输出，并用括号包裹，叶子节点省略子树部分。

五、复杂度分析

• 排序复杂度：使用快速排序，时间复杂度为 (O(n \log n))。
• 栈操作复杂度：每个节点入栈和出栈各一次，时间复杂度为 (O(n))。
• 总复杂度：(O(n \log n))，适用于 (n \leq 50000) 的数据规模。

该算法通过排序和栈操作高效地同时满足二叉搜索树和堆的性质，是Treap构造的经典实现方法。