# [POJ 1785] Binary Search Heap Construction【笛卡尔树】

• 2018-03-02
• 0
• 0

## Problem:

 Time Limit: 2000MS Memory Limit: 30000K

Description

Read the statement of problem G for the definitions concerning trees. In the following we define the basic terminology of heaps. A heap is a tree whose internal nodes have each assigned a priority (a number) such that the priority of each internal node is less than the priority of its parent. As a consequence, the root has the greatest priority in the tree, which is one of the reasons why heaps can be used for the implementation of priority queues and for sorting.

A binary tree in which each internal node has both a label and a priority, and which is both a binary search tree with respect to the labels and a heap with respect to the priorities, is called a treap. Your task is, given a set of label-priority-pairs, with unique labels and unique priorities, to construct a treap containing this data.

Input

The input contains several test cases. Every test case starts with an integer n. You may assume that 1<=n<=50000. Then follow n pairs of strings and numbers l1/p1,...,ln/pn denoting the label and priority of each node. The strings are non-empty and composed of lower-case letters, and the numbers are non-negative integers. The last test case is followed by a zero.

Output

For each test case output on a single line a treap that contains the specified nodes. A treap is printed as (< left sub-treap >< label >/< priority >< right sub-treap >). The sub-treaps are printed recursively, and omitted if leafs.

Sample Input

```7 a/7 b/6 c/5 d/4 e/3 f/2 g/1
7 a/1 b/2 c/3 d/4 e/5 f/6 g/7
7 a/3 b/6 c/4 d/7 e/2 f/5 g/1
0
```

Sample Output

```(a/7(b/6(c/5(d/4(e/3(f/2(g/1)))))))
(((((((a/1)b/2)c/3)d/4)e/5)f/6)g/7)
(((a/3)b/6(c/4))d/7((e/2)f/5(g/1)))
```

Source

Ulm Local 2004

## Code: O(Tnlogn) [3600K, 922MS]

```#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
using namespace std;

int n, tops;

struct Node{
char val[15];
int key;
Node *fa, *lc, *rc;

inline bool operator < (const Node &node2) const {return strcmp(val, node2.val) < 0;}

inline void clear() {fa = lc = rc = NULL;}
} CT[50005], *stk[50005];

inline void init(int n){
char *tmp = new char[25];
for(register int i = 1; i <= n; i++)
scanf("%s", tmp), sscanf(tmp, "%[^/]/%d", CT[i].val, &CT[i].key);
sort(CT + 1, CT + n + 1);  // BST Indexes must be ascending
delete []tmp;
}

inline void reset(int n) {for(register int i = 1; i <= n; i++) CT[i].clear();}

inline Node* build(int n){
memset(stk, 0, sizeof(stk)), tops = 0;
for(register int i = 1; i <= n; i++){
Node *o = NULL;
while(tops && CT[i].key > stk[tops]->key) o = stk[tops--];
CT[i].lc = o, CT[i].fa = stk[tops];
if(o) o->fa = &CT[i];
if(stk[tops]) stk[tops]->rc = &CT[i];
stk[++tops] = &CT[i];
}
return stk[1];
}

inline void inorder(Node *cur){
if(cur->lc) putchar('('), inorder(cur->lc), putchar(')');
printf("%s/%d", cur->val, cur->key);
if(cur->rc) putchar('('), inorder(cur->rc), putchar(')');
}

int main(){
while(scanf("%d", &n) != EOF && n){
init(n);
Node *root = build(n);
putchar('('), inorder(root), puts(")");
reset(n);  // Reset information of pointers
}
return 0;
}
```

#### 评论

darkleafin.cf
(该域名已过期且被抢注。。)
darkleafin.github.io

49750

https://github.com/Darkleafin

OPEN AT 2017.12.10

Please refresh the page if the code cannot be displayed normally.

https://visualgo.net/en

- Theme by Qzhai