Untitled

//trie
#include <iostream>
#include <string>

using namespace std;

class Node {
public:
	Node *child[26];
	// bool isLeaf;
	int count; //tuy de bai
	// string s;
	Node() {
		for (int i = 0; i < 26; i++) {
			child[i] = nullptr;
		}
		// isLeaf = false;
		count = 0;
	}
};
const int MAXNODE = 20000;
Node pool[MAXNODE];
int cnt;
Node *getNode() {
	return &pool[cnt++];
}

class Trie {
public:
	Node *root;
	Trie() {
		root = getNode();
	}
	void add(string s) {
		Node *cur = root;
		int index;
		for (char c : s) {
			index = c - 'a';
			if (cur->child[index] == nullptr) {
				cur->child[index] = getNode();
			}
			cur = cur->child[index];
			cur->count++;
		}
		// cur->isLeaf = true;
	}
	int findPrefix(string s) {
		Node * cur = root;
		int index;
		for (char c : s) {
			index = c - 'a';
			if (cur->child[index] == nullptr) return false;
			cur = cur->child[index];
		}
		return cur->count;
	}
};

int main() {
	cnt = 0;
	Trie t;
	t.add("abc");
	t.add("abcd");
	t.add("abd");
	t.add("ace");
	cout << "find prefix ab: " << t.findPrefix("ab") << endl;
	return 0;
}

//bst
#include <iostream>
#include <string>
#include <queue>
#include <vector>
#include <set>

using namespace std;
class Node {
public:
	int id;
	int score;
	Node(int i, int s) {
		id = i;
		score = s;
	}
};
class CmpNode {
public:
	bool operator() (const Node *n1, const Node *n2) {
		if (n2->score != n1->score) return n1->score < n2->score;
		return n1->id < n2->id;
	}
};
int main() {
	set<Node *, CmpNode> p;
	Node n1(1, 22);
	Node n2(2, 33);
	Node n3(3, 77);
	Node n4(4, 77);
	p.insert(&n1);
	p.insert(&n2);
	p.insert(&n3);
	p.insert(&n4);
	
	//p.erase(&n4);
	n4.score = 11;
	//p.insert(&n4);
	for (Node *tp : p) {
		printf("%d %d\n", tp->id, tp->score);
	}
	printf("\n\n");
	/*
	p.erase();
	p.find();
	p.upper_bound();
	p.lower_bound();
	p.begin();
	p.end();
	p.size();
	*/
	
	Node n(2, 33);
	auto it = p.upper_bound(&n);
	it--;
	printf("%d_%d\n", (*it)->id, (*it)->score);
	return 0;
}

//heap
#include <iostream>
#include <string>
#include <queue>
#include <vector>

using namespace std;
class Node {
public:
	int score;
	Node(int s) {
		score = s;
	}
};
class CmpNode {
public:
	bool operator() (const Node *n1, const Node *n2) {
		if (n2->score > n1->score) return true;
		else return false;
	}
};
int main() {
	priority_queue<Node *, vector<Node *>, CmpNode> p;
	Node n1(22);
	Node n2(33);
	Node n3(77);
	p.push(&n1);
	p.push(&n2);
	p.push(&n3);

	Node *tp = p.top();
	p.pop();
	tp = p.top();
	printf("%d\n", p.size());
	return 0;
}