9.2 traversal of binary tree
A1020
This topic examines the algorithm of building a tree from a middle order sequence and another traversal sequence. The key is to write the tree building function. Since we want to build a tree, the return value can be represented by node *. And because of recursive representation, we should pay attention to the end condition.
#include<cstdio>
#include<queue>
#include<algorithm>
using namespace std;
const int N = 30;
struct node
{
int data;
node* lchild;
node* rchild;
};
node* creatTree(int post[], int in[], int pl, int pr, int il, int ir)
{
if(pl > pr) return NULL;
node* root = new node;
int k;
for(k = il; k < ir; k++)
{
if(in[k] == post[pr]) break;
}
root->data = post[pr];
int numright = ir - k;
root->rchild = creatTree(post, in, pr- numright, pr - 1, k+1, ir);
root->lchild = creatTree(post, in, pl, pr - numright - 1, il, k - 1);
return root;
}
int num = 0, n;
int post[N], in[N];
void BFS(node* root)
{
queue<node*> qu;
qu.push(root);
while(! qu.empty())
{
node* now = qu.front();
qu.pop();
printf("%d", now->data);
num++;
if(num < n) printf(" ");
if(now->lchild != NULL) qu.push(now->lchild);
if(now->rchild != NULL) qu.push(now->rchild);
}
}
int main()
{
scanf("%d", &n);
for(int i = 0; i < n; i++)
scanf("%d", &post[i]);
for(int i = 0; i < n; i++)
scanf("%d", &in[i]);
node* root = creatTree(post, in, 0, n-1, 0, n-1);
BFS(root);
return 0;
}
A1086
This paper investigates the algorithm of using stack to simulate middle order and pre order traversal, so as to use two sequences to build a tree, and finally post order traversal. Since the traversal of middle order and pre order can be simulated by non recursive functions, we should first write out the element sequence of pop, observe which sequence it is, and finally build a tree by using the method of middle + other sequences.
What we should also pay attention to is how to deal with input and output. You can use strcmp to compare whether the first one is push or pop. If it is push, enter an x, otherwise press pop.
#include<cstdio>
#include<stack>
#include<cstring>
using namespace std;
const int N = 40;
struct node
{
int data;
node* lchild, *rchild;
};
int pre[N], in[N], preindex = 0, inindex = 0;
int n, num = 0;
node* createTree(int pl, int pr, int il, int ir)
{
if(pl > pr) return NULL;
node* root = new node;
root->data = pre[pl];
int k;
for(k = il; k <= ir; k++)
if(in[k] == pre[pl]) break;
int numleft = k - il;
root->lchild = createTree(pl+1, pl+numleft, il, k - 1);
root->rchild = createTree(pl+numleft+1, pr, k+1, ir);
return root;
}
void postorder(node* root)
{
if(root == NULL) return ;
postorder(root->lchild);
postorder(root->rchild);
printf("%d", root->data);
num++;
if(num < n) printf(" ");
}
int main()
{
scanf("%d", &n);
char str[5];
int x;
stack<int> st;
for(int i = 0; i < 2*n; i++)
{
scanf("%s", str);
if(strcmp(str, "Push") == 0)
{
scanf("%d", &x);
pre[preindex++] = x;
st.push(x);
}
else
{
in[inindex++] = st.top();
if( !st.empty()) st.pop();
}
}
node* root = createTree(0, n-1, 0, n-1);
postorder(root);
return 0;
}
A1102
This problem is to convert binary tree. The transformation binary tree is based on post order traversal. When you want to access the root node, the invite function is to exchange the left and right subtrees. Namely: swap(lchild,rchild). If you want to access the sequence traversal of the inverted binary tree, you can use the above method. There is also a simpler method: if the topic uses the first, middle and last order to access the binary tree, you can directly access the right subtree and then the left subtree in the function, and the others remain the same.
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
const int N = 50;
struct
{
int lchild, rchild;
}node[N];
int n, num1 = 0;
bool isroot[N];
int char2num(char c)
{
if(c == '-') return -1;
else
{
isroot[c - '0'] = false;
return c - '0';
}
}
int findroot()
{
for(int i = 0; i < n; i++)
if(isroot[i]) return i;
}
void postinvert(int root)
{
if(root == -1 ) return;
postinvert(node[root].lchild);
postinvert(node[root].rchild);
swap(node[root].lchild, node[root].rchild);
}
void level_Order(int root)
{
int num = 0;
queue<int> q;
q.push(root);
while(! q.empty())
{
int now = q.front();
q.pop();
printf("%d", now);
num++;
if(num < n) printf(" ");
else printf("\n");
if(node[now].lchild != -1) q.push(node[now].lchild);
if(node[now].rchild != -1) q.push(node[now].rchild);
}
}
void inorder(int root)
{
if(root == -1) return;
inorder(node[root].lchild);
printf("%d", root);
num1++;
if(num1 < n) printf(" ");
else printf("\n");
inorder(node[root].rchild);
}
int main()
{
memset(isroot, true, sizeof(isroot));
scanf("%d", &n);
char lchild, rchild;
for(int i = 0; i < n; i++)
{
scanf("%*c%c %c", &lchild, &rchild);
node[i].lchild = char2num(lchild);
node[i].rchild = char2num(rchild);
}
int root = findroot();
postinvert(root);
level_Order(root);
inorder(root);
return 0;
}
9.3 tree traversal
- Because ordinary trees are stored in vector array, they are generally written in loop during traversal. Because the loop has its own judgment condition, the end condition can not be added in dfs.
- If the traversal of ordinary trees needs to consider the hierarchy problem, if the weight of leaf nodes is not considered, a level array + vector array can be used to record the hierarchy and array.
A1079
This problem is a general tree traversal problem. First, we need to deal with the input-output problem. Because this problem needs to consider the weight of leaf nodes, it can be represented by a structure containing variables int and vector. Since the number of the tree has been given, you can use the writing method of structure array (static linked list). When entering, judge whether to enter leaf node or sales volume in the subsequent order according to the size of k. In addition, because the depth should be considered, a depth variable can be added to preorder to record the depth.
#include<cstdio>
#include<vector>
#include<cmath>
using namespace std;
const int N = 100010;
struct node
{
int data;
vector<int> child;
}Node[N];
int n;
double p, r, ans = 0;
void preorder(int root, int depth)
{
if(Node[root].child.size() == 0)
{
ans += pow(1+r, depth)* Node[root].data * p;
}
else
{
for(int i = 0; i < Node[root].child.size(); i++)
{
preorder(Node[root].child[i], depth+1);
}
}
}
int main()
{
int k, child;
scanf("%d%lf%lf", &n, &p, &r);
r /= 100;
for(int i =0; i < n; i++)
{
scanf("%d", &k);
if(k != 0)
{
for(int j = 0; j < k; j++)
{
scanf("%d", &child);
Node[i].child.push_back(child);
}
}
else
{
scanf("%d", &Node[i].data);
}
}
preorder(0, 0);
printf("%.1f", ans);
return 0;
}
A1090
This question is no different from 1079. It is all about traversal of trees. As long as the maximum depth and the number of nodes with the maximum depth are found, the weight problem does not need to be considered, so the tree can be represented by vectornode[N]. At this time, the condition for judging whether the tree is a leaf node is node [i] size()==0. Therefore, in recursion, if it is a leaf node, compare it with the maximum depth. If it is greater than, update it. If it is equal, update num, otherwise exit. If it is not a leaf node, continue recursion.
#include<cstdio>
#include<vector>
#include<cmath>
using namespace std;
const int N = 100010;
vector<int> Node[N];
int n, maxdepth = -1, num = 0;
double p, r;
void preorder(int root, int depth)
{
if(Node[root].size() == 0)
{
if(maxdepth < depth)
{
maxdepth = depth;
num = 1;
}
else if(maxdepth == depth)
num++;
return;
}
for(int i = 0; i < Node[root].size(); i++)
{
preorder(Node[root][i], depth+1);
}
}
int main()
{
int parent, root;
scanf("%d%lf%lf", &n, &p, &r);
r /= 100;
for(int i = 0; i < n; i++)
{
scanf("%d", &parent);
if(parent == -1) root = i;
else Node[parent].push_back(i);
}
preorder(root, 0);
printf("%.2f %d", pow(1+r, maxdepth)*p, num);
return 0;
}
A1094
This question is to find the maximum number of knots on the same floor. It can be written in dfs or bfs.
Note:
- Since the starting node is 1, the subscript of the node is from 1 to N, and the traversal should be ≤ n, otherwise an error will occur when the test case has only one node.
- You can set the structure and add the layer variable to the structure. However, since you do not need to consider the weight of the node, you can also use the vector array to represent the node and define two arrays. One array levelnumber is the mapping from the number of layers to the number of nodes in the layer, and the other array h is the mapping from the number of nodes to the number of layers. The access node in bfs or dfs is. Add 1 to the number of layers of the node, that is, level number [H [ID]] +.
- The given code writes both dfs and bfs, and calls any one.
#include<cstdio>
#include<vector>
#include<cstring>
#include<queue>
using namespace std;
const int N = 110;
vector<int> Node[N];
int n, m;
int levelNumber[N];
int h[N];
void DFS(int root)
{
levelNumber[h[root]]++;
for(int i = 0; i < Node[root].size(); i++)
{
int child = Node[root][i];
h[child] = h[root]+1;
DFS(child);
}
}
void BFS()
{
queue<int> q;
q.push(1);
while(!q.empty())
{
int now = q.front();
levelNumber[h[now]]++;
q.pop();
for(int i = 0; i < Node[now].size(); i++)
{
int child = Node[now][i];
h[child] = h[now]+1;
q.push(child);
}
}
}
int main()
{
int parent, k, child;
memset(levelNumber, 0, sizeof(levelNumber));
memset(h, 0, sizeof(h));
scanf("%d%d", &n, &m);
for(int i = 0; i < m; i++)
{
scanf("%d%d", &parent, &k);
for(int j = 0; j < k; j++)
{
scanf("%d", &child);
Node[parent].push_back(child);
}
}
h[1] = 1;
DFS(1);
int level = 1, number = -1;
for(int i = 1; i <= n; i++)
{
if(levelNumber[i] > number)
{
number = levelNumber[i];
level = i;
}
}
printf("%d %d", number, level);
return 0;
}
A1106
This problem is to find the tree with the smallest depth. Note that a large value should be set at the beginning of mindepth.
#include<cstdio>
#include<vector>
#include<cmath>
using namespace std;
const int N = 100010;
vector<int> Node[N];
int h[N];
int n, mindepth = N, num = 0;
double p, r;
void DFS(int root)
{
if(Node[root].size() == 0)
{
if(h[root] < mindepth)
{
mindepth = h[root];
num = 1;
}
else if(h[root] == mindepth)
num++;
}
for(int i = 0; i < Node[root].size(); i++)
{
int child = Node[root][i];
h[child] = h[root]+1;
DFS(child);
}
}
int main()
{
scanf("%d%lf%lf", &n, &p, &r);
r /= 100;
int child, k;
for(int i = 0; i < n; i++)
{
scanf("%d", &k);
for(int j = 0; j < k; j++)
{
scanf("%d", &child);
Node[i].push_back(child);
}
}
h[0] = 0;
DFS(0);
printf("%.4f %d", pow(1+r, mindepth)*p, num);
return 0;
}
A1004
The idea of this question is similar to that of 1094, which is to find the number of satisfying conditions at the same level, but this question is a little more difficult than 1094, because 1094 only needs to find the maximum value, so you can directly traverse all layers without finding the maximum number of layers, but this question needs to be output one by one, so you need to find the maximum number of layers.
- If the maximum number of layers is found, it should be noted that maxdepth should be the same as the value set for the first layer at first. If the first layer is set to 1, maxdepth is also 1. Otherwise, maxdepth will not be updated due to special data (1, 0) and will not be output
- Without weights, consider using the level number array to establish the mapping from layers to numbers, and the h array to establish the mapping from nodes to layers. Store tree nodes with vector array.
#include<cstdio>
#include<vector>
#include<queue>
using namespace std;
const int N = 110;
vector<int> Node[N];
int levelnumber[N];
int h[N];
int maxdepth = 1;
void BFS()
{
queue<int> q;
q.push(1);
while(!q.empty())
{
int now = q.front();
q.pop();
if(Node[now].size() == 0)
levelnumber[h[now]]++;
else
{
for(int i = 0; i < Node[now].size(); i++)
{
int child = Node[now][i];
h[child] = h[now]+1;
if(h[child] > maxdepth)
maxdepth = h[child];
q.push(child);
}
}
}
}
int main()
{
int n, m;
int parent, k, child;
scanf("%d%d", &n, &m);
for(int i = 0; i < m; i++)
{
scanf("%d%d", &parent, &k);
for(int j = 0; j < k; j++)
{
scanf("%d", &child);
Node[parent].push_back(child);
}
}
h[1] = 1;
BFS();
for(int i = 1; i <= maxdepth; i++)
{
printf("%d", levelnumber[i]);
if(i != maxdepth) printf(" ");
}
return 0;
}
A1053
This problem is the traversal of the tree, but you need to search with dfs. One thing to note is that there may be two child nodes with equal weights under a node, so you can't sort first. You need to store all the results before sorting.
#include<cstdio>
#include<queue>
#include<vector>
#include<algorithm>
using namespace std;
const int N = 110;
int n, m, s;
vector<int> temp;
vector<vector<int> > ans;
struct node
{
int weight;
vector<int>child;
}Node[N];
bool cmp(vector<int>a, vector<int> b)
{
int size = min(a.size(), b.size());
for(int i = 0; i < size; i++)
{
if(a[i] != b[i]) return a[i] > b[i];
}
}
int path[N];
void DFS(int index, int now)
{
if(now == s && Node[index].child.size() == 0 )
{
ans.push_back(temp);
return ;
}
if(now > s || Node[index].child.size() == 0) return ;
for(int i = 0; i < Node[index].child.size(); i++)
{
int child = Node[index].child[i];
temp.push_back(Node[child].weight);
DFS(child, now + Node[child].weight);
temp.pop_back();
}
}
int main()
{
scanf("%d%d%d", &n, &m, &s);
for(int i = 0; i < n; i++)
scanf("%d", &Node[i].weight);
int parent, k, child;
for(int i = 0; i < m; i++)
{
scanf("%d%d", &parent, &k);
for(int j = 0; j < k; j++)
{
scanf("%d", &child);
Node[parent].child.push_back(child);
}
}
temp.push_back(Node[0].weight);
DFS(0,Node[0].weight);
sort(ans.begin(), ans.end(), cmp);
for(int i = 0; i < ans.size(); i++)
{
for(int j = 0; j < ans[i].size(); j++)
{
printf("%d", ans[i][j]);
if(j != ans[i].size() - 1) printf(" ");
}
printf("\n");
}
return 0;
}
9.4 binary lookup tree
- Binary search tree has a property: the middle order traversal is an ordered sequence. Therefore, any given traversal sequence can uniquely establish a binary tree. When a sequence is given, because the first node is the root node, you can build a tree by circular insertion or write a function by using the method of ordinary binary tree.
- The mirror tree of a binary tree actually traverses the right subtree first and then the left subtree
A1043
First build a tree according to the sequence. Because the given sequence is a preorder sequence, you can use the circular insertion method to build a tree. When the tree is built, write the preorder and premoder functions. Then compare temp with pre and prem. If yes, output post or post. Otherwise, output no.
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
const int N = 1010;
struct node
{
int data;
node*lchild, *rchild;
};
int n;
void insert(node* & root, int x)
{
if(root == NULL)
{
root = new node;
root->data = x;
root->lchild = root->rchild = NULL;
return;
}
else if(x < root->data)
insert(root->lchild, x);
else
insert(root->rchild, x);
}
vector<int> temp, pre, preM, post, postM;
void preorder(node* root, vector<int>& vi)
{
if(root == NULL) return;
vi.push_back(root->data);
preorder(root->lchild, vi);
preorder(root->rchild, vi);
}
void postOrder(node* root, vector<int>& vi)
{
if(root == NULL) return;
postOrder(root->lchild, vi);
postOrder(root->rchild, vi);
vi.push_back(root->data);
}
void preMorder(node* root, vector<int>& vi)
{
if(root == NULL) return ;
vi.push_back(root->data);
preMorder(root->rchild, vi);
preMorder(root->lchild, vi);
}
void postMorder(node* root, vector<int>& vi)
{
if(root == NULL) return;
postMorder(root->rchild, vi);
postMorder(root->lchild, vi);
vi.push_back(root->data);
}
int main()
{
int tmp;
node* root = NULL;
scanf("%d", &n);
for(int i = 0; i < n; i++)
{
scanf("%d", &tmp);
temp.push_back(tmp);
insert(root, tmp);
}
preorder(root, pre);
preMorder(root, preM);
postOrder(root, post);
postMorder(root, postM);
if(temp == pre)
{
printf("YES\n");
for(int i = 0; i < post.size(); i++)
{
printf("%d", post[i]);
if(i != post.size() - 1) printf(" ");
else printf("\n");
}
}
else if(temp == preM)
{
printf("YES\n");
for(int i = 0; i < postM.size(); i++)
{
printf("%d", postM[i]);
if(i != postM.size() - 1) printf(" ");
else printf("\n");
}
}
else printf("NO\n");
return 0;
}
A1064
This question examines how to store a given sequence in an array and build a CBT, using two knowledge points.
- The middle order traversal of BST is an increasing sequence
- When a complete binary lookup tree is stored in an array, the incremental output is sequence traversal.
Based on the above contents, first sort the given array incrementally, * * because the middle order of bst is incrementally, you can use the middle order to traverse and build the tree. When accessing a node, you assign a value to the node** Then output the array in sequence, which is sequence traversal.
#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;
const int N = 1010;
int n, index = 0;
int tmp[N], CBT[N];
void inorder(int root)
{
if(root > n) return;
if(root * 2 <= n)
inorder(root*2);
CBT[root] = tmp[index++];
if(root*2 + 1 <= n)
inorder(root*2+1);
}
void BFS()
{
int num = 0;
queue<int> q;
q.push(1);
while(!q.empty())
{
int now = q.front();
printf("%d", CBT[now]);
q.pop();
num++;
if(num < n) printf(" ");
if(now*2 <= n) q.push(now*2);
if(now*2 +1 <= n) q.push(now*2+1);
}
}
int main()
{
scanf("%d", &n);
for(int i = 0; i < n; i++)
scanf("%d", &tmp[i]);
sort(tmp, tmp+n);
inorder(1);
BFS();
return 0;
}
A1099
This problem is essentially the same as the idea of 1064. It uses the property of increasing order traversal in binary search tree to build a tree during middle order traversal. However, 1064 is a complete binary tree, which can be stored in an array, and this problem is an ordinary binary tree, so it needs to be implemented with a structure.
```cpp
#include<cstdio>
#include<queue>
#include<algorithm>
using namespace std;
const int N = 110;
struct node
{
int data;
int lchild, rchild;
}Node[N];
int tmp[N], index = 0, n;
void inorder(int root)
{
if(root == -1) return ;
inorder(Node[root].lchild);
Node[root].data = tmp[index++];
inorder(Node[root].rchild);
}
void BFS()
{
int num = 0;
queue<int> q;
q.push(0);
while(!q.empty())
{
int now = q.front();
q.pop();
printf("%d", Node[now].data);
num++;
if(num != n) printf(" ");
else printf("\n");
if(Node[now].lchild != -1) q.push(Node[now].lchild);
if(Node[now].rchild != -1) q.push(Node[now].rchild);
}
}
int main()
{
int lchild, rchild;
scanf("%d", &n);
for(int i = 0; i < n; i++)
{
scanf("%d%d", &lchild, &rchild);
Node[i].lchild = lchild;
Node[i].rchild = rchild;
}
for(int i = 0; i < n; i++)
scanf("%d", &tmp[i]);
sort(tmp, tmp + n);
inorder(0);
BFS();
return 0;
}
``
9.3 AVL tree
A1066
This topic examines the establishment of avl tree (circular insertion), that is, how to balance the height during insertion, which belongs to the template problem.
#include<cstdio>
#include<algorithm>
using namespace std;
const int N = 30;
struct node
{
int data;
int height;
node* lchild, *rchild;
};
int getHeight(node* root)
{
if(root == NULL) return 0;
else return root->height;
}
void updateHeight(node* root)
{
root->height = max(getHeight(root->lchild), getHeight(root->rchild)) + 1;
}
int getBalanceFactor(node* root)
{
return getHeight(root->lchild) - getHeight(root->rchild);
}
void L(node* & root)
{
node* temp = root->rchild;
root->rchild = temp->lchild;
temp->lchild = root;
updateHeight(root);
updateHeight(temp);
root = temp;
}
void R(node* & root)
{
node* temp = root->lchild;
root->lchild = temp->rchild;
temp->rchild = root;
updateHeight(root);
updateHeight(temp);
root = temp;
}
void insert(node* & root, int x)
{
if(root == NULL)
{
root = new node;
root->data = x;
root->height = 1;
root->lchild = root->rchild = NULL;
return ;
}
else if(x < root->data)
{
insert(root->lchild, x);
updateHeight(root->lchild);
if(getBalanceFactor(root) == 2)
{
if(getBalanceFactor(root->lchild) == 1)
{
R(root);
}
else if(getBalanceFactor(root->lchild) == -1)
{
L(root->lchild);
R(root);
}
}
}
else
{
insert(root->rchild, x);
updateHeight(root->rchild);
if(getBalanceFactor(root) == -2)
{
if(getBalanceFactor(root->rchild) == 1)
{
R(root->rchild);
L(root);
}
else if(getBalanceFactor(root->rchild) == -1)
{
L(root);
}
}
}
}
int main()
{
int n;
int a[N];
node* root = NULL;
scanf("%d", &n);
for(int i = 0; i < n; i++)
{
scanf("%d", &a[i]);
insert(root, a[i]);
}
printf("%d", root->data);
return 0;
}
9.6 concurrent query
Parallel search set is realized by array, and its structure is the same as that of tree. Is an application of tree.
A1107
This topic is a topic about parallel search. Because everyone has different interests, the first one who is interested is used to be the person in charge of this interest. Then merge the current person with the collection of the person in charge of the same interest. As long as one interest is the same, it can be merged, so we need to establish the mapping from interest to person in charge and the collection between people. When the current person reads an interest, if the interest is already in charge, add it to the collection where the person in charge is located. Namely: Union (I, findpath (course [k]);
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 1010;
int father[N], course[N];
int isfather[N];
bool cmp(int a, int b)
{
return a > b;
}
void init(int n)
{
for(int i = 1; i <= n; i++)
father[i] = i;
memset(course, 0, sizeof(course));
}
int findfather(int a)
{
int x = a;
while(a != father[a])
a = father[a];
while(x != father[x])
{
int z = x;
x = father[x];
father[z] = a;
}
return a;
}
void Union(int a, int b)
{
int fa = findfather(a);
int fb = findfather(b);
if(fa != fb)
{
father[fa] = fb;
}
}
int main()
{
int n, k, tmp;
scanf("%d", &n);
init(n);
for(int i = 1; i <= n; i++)
{
scanf("%d:", &k);
for(int j = 0; j < k; j++)
{
scanf("%d", &tmp);
if(course[tmp] == 0)
course[tmp] = i;
Union(i, findfather(course[tmp]));
}
}
for(int i = 1; i <= n; i++)
{
isfather[findfather(i)]++;
}
int ans = 0;
for(int i = 1; i <= n; i++)
{
if(isfather[i] != 0) ans++;
}
printf("%d\n", ans);
sort(isfather+1, isfather+n+1, cmp);
for(int i = 1; i <= ans; i++)
{
printf("%d", isfather[i]);
if(i != ans) printf(" ");
}
return 0;
}
9.7 reactor
Heap is generally implemented by array. It is defined as the value of the root node greater than (or less than) the child node. Its structure is similar to binary tree. It is an application of binary tree.
Heap building: adjust the non leaf nodes upside down, that is, adjust down adjust (i,n) from n/2~1.
Delete the heap top: cover the heap top with the last node, and then adjust (1,n-1) downward
Insert node: insert the node into the last element of the array, and then adjust the last node upward, upadjust(1,n+1).
Heap sorting: operate the established heap. Since the top of the heap is the largest element, call the element at the top of the heap with the last element, and then adjust the downadjust(1,n-1), and so on until it is adjusted to 1 ~ 1 in the heap.
A1098
This is a basic template question. You only need to design whether the arrays are the same in sorting. If they are the same, they will be output.
There is also a trap in this problem. The initial sequence cannot be counted as equal, because if the initial sequence is equal, there may be a situation where both methods can be done and multiple solutions can be obtained.
#include<cstdio>
#include<algorithm>
using namespace std;
const int N = 110;
int n;
int a[N], b[N], heap[N];
bool flag = false;
bool cmp(int a, int b)
{
return a < b;
}
bool isSame(int a[], int b[])
{
for(int i = 1; i <= n; i++)
if(a[i] != b[i]) return false;
return true;
}
void disp(int a[])
{
for(int i = 1; i <= n; i++)
{
printf("%d", a[i]);
if(i != n) printf(" ");
}
}
void InsertionSort()
{
bool print = false;
for(int i = 2; i <= n; i++)
{
if(i != 2 &&isSame(a, b))
{
printf("Insertion Sort\n");
print = true;
}
sort(a+1, a + i + 1, cmp);
if(print)
{
disp(a);
flag = true;
return ;
}
}
}
void downadjust(int low, int high)
{
int i = low, j = i * 2;
while(j <= high)
{
if(j+1 <= high && heap[j+1] > heap[j])
j = j + 1;
if(heap[j] > heap[i])
{
swap(heap[j], heap[i]);
i = j;
j = i * 2;
}
else break;
}
}
void HeapSort()
{
bool print = false;
for(int i = n/2; i >= 1; i--)
downadjust(i, n);
for(int i = n; i >= 2; i--)
{
if(i != n && isSame(b, heap))
{
printf("Heap Sort\n");
print = true;
}
swap(heap[1], heap[i]);
downadjust(1, i - 1);
if(print)
{
disp(heap);
return ;
}
}
}
int main()
{
scanf("%d", &n);
for(int i = 1; i <= n; i++)
{
scanf("%d", &a[i]);
heap[i] = a[i];
}
for(int i = 1; i <= n; i++)
{
scanf("%d", &b[i]);
}
InsertionSort();
if(!flag) HeapSort();
return 0;
}