斜堆是个很有趣的东西。而且它有一些很有意思的性质。
斜堆的大概就是每次往堆里面插入一个元素的操作非常“有趣”。插入的节点从根节点开始。如果插入的元素值比所在根小，它会将根“挤下去”，即替代原先的根的位置，将原先的根连到它的左子树上。如果所在根节点为空，它直接插入到此节点上。如果插入的元素比根大，那么它就会先交换所在根的两个子树，然后再递归到原先根的左子树进行插入，直到它比所在根小或者所在根为空。
我们知道根是一个二叉树。根据斜堆的定义，我们可以大概推测它的几个明显的性质：
- 斜堆是一个小根堆
- 斜堆上的任意一个节点有可能是一个完全二叉树或一个不完全二叉树，当且仅当它的左子树大于它的右子树。
根据以上性质，我们可以得出“斜堆上任意一个节点若有右子树必定有左子树”的结论。证明显然。
然后，我们就会发现几个不得了的性质：
- 对于一个斜堆，它最后插入的节点一定在它的最左边的链上。
- 若有一个节点没有右子树，并且它的左子节点拥有左节点，那么这个节点必定是最后插入的节点。
- 对于没有符合性质4的节点的斜堆，它最后插入的节点一定是最左边链的最深端点。
后三个性质可以轻易得到斜堆最后插入的节点位置，这就是我们解这道题的关键了：倒着推，每次删除最后插入的节点，将为了插入该节点而交换子树的节点交换回来。每删除一个节点后得到的新的堆就可以再次用相同的方法做了，直到堆中只剩一个节点或者堆中没有节点（看心情）。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
| #include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn=52;
inline int read()
{
int x=0;bool w=0;char c=getchar();
while(!isdigit(c))w|=c=='-',c=getchar();
while(isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=getchar();
return w?-x:x;
}
int n,ans[maxn],root;
int son[maxn][2],fa[maxn],node[maxn];
int main()
{
n=read();
for(int i=1;i<=n;i++){
int x=read();
son[x%100][x/100]=i;
fa[i]=x%100;
}
root=0;
int tot=0;
while(son[root][0]){
int now=root;
while(son[now][0]){
if(!son[now][1] and son[son[now][0]][0])
break;
now=son[now][0];
}
if(now!=root){
ans[++tot]=now;
now=fa[now];
fa[son[now][0]]=0;
son[now][0]=son[son[now][0]][0];
if(son[now][0])
fa[son[now][0]]=now;
while(now!=root){
swap(son[now][0],son[now][1]);
now=fa[now];
}
swap(son[root][0],son[root][1]);
}else{
ans[++tot]=now;
root=son[root][0];
fa[root]=0;
}
}
ans[++tot]=root;
for(int i=tot;i>0;i--)printf("%d ",ans[i]);
return 0;
}
|
当然也可以用dfs求解。
