堆、二叉搜索树



前言

其实这两个主要是为了接下来的一种叫做Splay的数据结构（听说很厉害）

  1. 堆
    http://www.cnblogs.com/chenweichu/articles/5710635.html
    http://www.cnblogs.com/chenweichu/articles/5710567.html
  2. 二叉搜索树
    https://www.cnblogs.com/yym2013/p/3552800.html

题外话·堆 - HihoCoder - 1105


思路
堆的模板题 直接打法：

	#include <cstdio>
	#include <algorithm>
	using namespace std;
	const int N = 1e5 + 15;

	int h[N];
	int tot;

	void pushDown(int id){
		for(int idt; 2*id <= tot; id = idt){
			idt = (h[2*id] > h[id]) ? 2*id : id;	//左右子树中取最大
			idt = (2*id + 1 <= tot && h[2*id + 1] > h[idt]) ? 2*id + 1 : idt;

			if(id == idt)   break;

			swap(h[id], h[idt]);
			id = idt;
		}
	}

	void pushUp(int id){
		while(id != 1){
			if(h[id] < h[id/2])     break;
			swap(h[id], h[id/2]);	//比父节点大就不断与父节点交换
			id >>= 1;
		}
	}

	int getAndPop(){
		int ans = h[1];
		swap(h[1], h[tot]);
		tot--;
		pushDown(1);
		return ans;
	}

	int main(){
		int q;
		tot = 0;
		scanf("%d",&q);
		while(q--){
			char op[2];
			int num;
			scanf("%s", op);
			if(op[0] == 'A'){
				scanf("%d", &num);
				h[++tot] = num;
				pushUp(tot);
			}else{
				printf("%d\n", getAndPop());
			}
		}

		return 0;
	}

封装为类，作优先队列用：

	#include <cstdio>
	#include <algorithm>
	using namespace std;
	const int N = 1e5 + 15;

	struct hp{
		int h[N];
		int tot;

		hp(): tot(0) {}
		void push(int num){
			h[++tot] = num;
			pushUp(tot);
		}
		void pop(){
			swap(h[1], h[tot--]);
			pushDown(1);
		}
		int  top()   { return h[1]; }
		bool empty() { return tot == 0; }
		void clear() { tot = 0; }

		void pushDown(int id){
			for(int idt; 2*id <= tot; id = idt){
				idt = (h[2*id] > h[id]) ? 2*id : id;
				idt = (2*id + 1 <= tot && h[2*id + 1] > h[idt]) ? 2*id + 1 : idt;

				if(id == idt)   break;

				swap(h[id], h[idt]);
				id = idt;
			}
		}

		void pushUp(int id){
			while(id != 1){
				if(h[id] < h[id/2])     break;
				swap(h[id], h[id/2]);
				id >>= 1;
			}
		}
	};

	hp que;

	int main(){
		int q;
		scanf("%d",&q);
		que.clear();
		while(q--){
			char op[2];
			int num;
			scanf("%s", op);
			if(op[0] == 'A'){
				scanf("%d", &num);
				que.push(num);
			}else{
				printf("%d\n", que.top());
				que.pop();
			}
		}
	}


二叉搜索树 - HDU - 3791

思路
BST模板题

	#include <cstdio>
	#include <algorithm>
	#include <cstring>
	using namespace std;
	const int N = 1024;

	int t1[N], t2[N];
	char s[N], t[N];

	void push(int x[], int num, int rt){
		if(x[rt] == -1){	//父节点无值填父节点，否则按定义用dfs填写
			x[rt] = num;
		}else if(num < x[rt]){
			push(x, num, rt << 1);
		}else{
			push(x, num, rt << 1 | 1);
		}
	}

	bool judge(){
		for(int i = 0; i < N; i++){
			if(t1[i] != t2[i])  return false;
		}
		return true;
	}

	int main(){
		int n;
		while(scanf("%d", &n) && n){
			memset(t1, -1, sizeof(t1));
			scanf("%s", s);
			for(int i = 0; s[i]; i++)       push(t1, s[i] - '0', 1);

			while(n--){
				memset(t2, -1, sizeof(t2));
				scanf("%s", t);
				for(int i = 0; t[i]; i++)   push(t2, t[i] - '0', 1);
				puts(judge() ? "YES" : "NO");
			}
		}
	}