数据结构-Trie、并查集、堆

Trie通常有两种写法，一种是竞赛常用的数组表示，另一种问更直观的结构体表示

数组：acwing835

void insert(string& str)
{
int curr = 0;
for (int i = 0; i < str.size(); i++)
{
if (!son[curr][str[i] - 'a'])
son[curr][str[i] - 'a'] = ++index; //一定是++index
curr = son[curr][str[i] - 'a'];
}
cnt[curr]++; //索引是curr不是index
}

int query(string& str)
{
int curr = 0;
for (int i = 0; i < str.size(); i++)
{
if (!son[curr][str[i] - 'a'])
return 0;
curr = son[curr][str[i] - 'a'];
}
return cnt[curr]; //索引是curr不是index
}

int main()
{
int n;
cin >> n;
while (n--)
{
char ch;
string str;
cin >> ch >> str;
if (ch == 'I')
insert(str);
else
cout << query(str) << endl;
}
return 0;
}

结构体

#define alpha 26

typedef struct treeNode
{
struct treeNode* children[alpha];
bool is_end;
}treenode;

treenode* createnode()
{
treenode* p = new treenode;
p->is_end = false;
for (int i = 0; i < alpha; i++)
{
p->children[i] = NULL;
}
return p;
}

void insertnode(treenode* root, const string str)
{
treenode* now = root;
for (int i = 0; i < str.size(); i++)
{
int index = str[i] - 'a';
if (now->children[index] == NULL)
{
now->children[index] = createnode();
}
now = now->children[index];
}
now->is_end = true;
}

bool findnode(treenode* root, const string str)
{
treenode* now = root;
for (int i = 0; i < str.size(); i++)
{
int index = str[i] - 'a';
if (now->children[index] == NULL)
{
return false;
}
now = now->children[index];
}
return now->is_end;
}

int main()
{
treenode* root = createnode();
insertnode(root, "apple");
if (findnode(root, "apple"))
cout << true;
else
cout << false;
return 0;
}

并查集

例题：acwing836

const int N = 100010;
int set[N];

int find(int num)
{
if (set[num] < 0)
return num;
return set[num] = find(set[num]);
}

void merge(int num1, int num2)
{
int f1 = find(num1);
int f2 = find(num2);
if (f1 == f2)
return;
if (set[f1] < set[f2])
set[f2] = f1;
else if (set[f1] > set[f2])
set[f1] = f2;
else
{
set[f2]--; //注意一定是高度增加在先！
set[f1] = f2;
}
}
int main()
{
int n, m;
cin >> n >> m;
for (int i = 0; i < n; i++)
{
set[i] = -1;
}
while (m--)
{
string str;
int a, b;
cin >> str >> a >> b;
if (str == "M")
merge(a, b);
else
cout << ((find(a) == find(b)) ? "Yes" : "No") << endl;
}
return 0;
}

堆

堆排序：acwing838

const int N = 100010;
int heap[N];
int sz = 0;

void Swap(int a, int b)
{
swap(heap[a], heap[b]);
}

void up(int index)
{
int curr = index;
while (curr / 2 && heap[curr] < heap[curr / 2])
{
Swap(curr, curr / 2);
curr /= 2;
}
}

void insert(int num)
{
heap[++sz] = num;
up(sz);
}

void down(int index)
{
int curr = index;
if (index * 2 <= sz && heap[index * 2] < heap[curr]) //注意index和curr的使用
curr = index * 2;
if (index * 2 + 1 <= sz && heap[index * 2 + 1] < heap[curr])
curr = index * 2 + 1;
if (curr == index)
return;
Swap(curr, index);
down(curr);
}

int main()
{
int n, m;
cin >> n >> m;
for (int i = 0; i < n; i++)
{
int num;
cin >> num;
insert(num);
}
for (int i = 0; i < m; i++)
{
cout << heap[1] << ' ';
Swap(1, sz);
sz--;
down(1);
}
return 0;
}

模拟堆：acwing839

const int N = 100010;
int heap[N];
int h[N];
int p[N];
int pos = 0;
int sz = 0;

void Swap(int index1, int index2)
{
swap(h[p[index1]], h[p[index2]]); //三者的顺序需要注意
swap(heap[index1], heap[index2]);
swap(p[index1], p[index2]);
}

void up(int index)
{
int curr = index;
while (curr / 2 && heap[curr] < heap[curr / 2])
{
Swap(curr, curr / 2);
curr /= 2;
}
}

void down(int index)
{
int curr = index;
if (index * 2 <= sz && heap[index * 2] < heap[curr])
curr = index * 2;
if (index * 2 + 1 <= sz && heap[index * 2 + 1] < heap[curr])
curr = index * 2 + 1;
if (curr == index)
return;
Swap(curr, index);
down(curr); //down在交换下面，且需要down的索引是curr
}

void pop_min()
{
Swap(1, sz);
sz--;
down(1);
}

void pop(int index)
{
int curr = h[index];
Swap(curr, sz);
sz--;
up(curr);
down(curr);
}

void insert(int num)
{
heap[++sz] = num;
h[++pos] = sz;
p[sz] = pos;
up(sz);
}

void change(int index, int num)
{
heap[h[index]] = num;
up(h[index]);
down(h[index]);
}

int main()
{
int n;
cin >> n;
while (n--)
{
string str;
cin >> str;
if (str == "I")
{
int num;
cin >> num;
insert(num);
}
else if (str == "PM")
cout << heap[1] << endl;
else if (str == "DM")
pop_min();
else if (str == "D")
{
int index;
cin >> index;
pop(index);
}
else
{
int a, b;
cin >> a >> b;
change(a, b);
}
}
return 0;
}