[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

Solution:

本题是笛卡尔树 O(n) 建树模板。

笛卡尔树是一种与 Treap 类似的 BST,由两个键值 valkey 组成。

其中 val 符合二叉排序树性质(即中序遍历升序),key 符合大根堆性质。

与 Treap 不同的是,笛卡尔树的 key 值是确定的,并不是随机给出的。但是两者建树操作相同。

建树时,首先保证 val 升序,然后用一个 key 值单调递减的单调栈来维护树的右链,寻找合适的位置插入,保证 key 符合堆的性质。图示如下:

注意边界条件,防止访问空指针以及之前的操作中残留的无效数据

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

常年不在线的QQ:
49750

不定期更新的GitHub:
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