【算法笔记自学】第 9 章 提高篇（3）——数据结构专题（2）

9.1树与二叉树

#include <cstdio>int main() {int n, m;scanf("%d%d", &n, &m);printf(n == m + 1 ? "Yes" : "No");return 0;
}

9.2二叉树的遍历

#include <cstdio>
#include <vector>
using namespace std;const int MAXN = 50;struct Node {int l, r;
} nodes[MAXN];vector<int> pre;void preOrder(int root) {if (root == -1) {return;}pre.push_back(root);preOrder(nodes[root].l);preOrder(nodes[root].r);
}int main() {int n;scanf("%d", &n);for (int i = 0; i < n; i++) {scanf("%d%d", &nodes[i].l, &nodes[i].r);}preOrder(0);for (int i = 0; i < (int)pre.size(); i++) {printf("%d", pre[i]);if (i < (int)pre.size() - 1) {printf(" ");}}return 0;
}

#include <cstdio>
#include <vector>
using namespace std;const int MAXN = 50;struct Node {int l, r;
} nodes[MAXN];vector<int> pre;void preOrder(int root) {if (root == -1) {return;}preOrder(nodes[root].l);pre.push_back(root);preOrder(nodes[root].r);
}int main() {int n;scanf("%d", &n);for (int i = 0; i < n; i++) {scanf("%d%d", &nodes[i].l, &nodes[i].r);}preOrder(0);for (int i = 0; i < (int)pre.size(); i++) {printf("%d", pre[i]);if (i < (int)pre.size() - 1) {printf(" ");}}return 0;
}

#include <cstdio>
#include <vector>
using namespace std;const int MAXN = 50;struct Node {int l, r;
} nodes[MAXN];vector<int> pre;void preOrder(int root) {if (root == -1) {return;}preOrder(nodes[root].l);preOrder(nodes[root].r);pre.push_back(root);
}int main() {int n;scanf("%d", &n);for (int i = 0; i < n; i++) {scanf("%d%d", &nodes[i].l, &nodes[i].r);}preOrder(0);for (int i = 0; i < (int)pre.size(); i++) {printf("%d", pre[i]);if (i < (int)pre.size() - 1) {printf(" ");}}return 0;
}

#include <cstdio>
#include <vector>
#include <queue>
using namespace std;const int MAXN = 50;struct Node {int l, r;
} nodes[MAXN];vector<int> layer;void layerOrder(int root) {queue<int> q;q.push(root);while (!q.empty()) {int front = q.front();q.pop();layer.push_back(front);if (nodes[front].l != -1) {q.push(nodes[front].l);}if (nodes[front].r != -1) {q.push(nodes[front].r);}}
}int main() {int n;scanf("%d", &n);for (int i = 0; i < n; i++) {scanf("%d%d", &nodes[i].l, &nodes[i].r);}layerOrder(0);for (int i = 0; i < (int)layer.size(); i++) {printf("%d", layer[i]);if (i < (int)layer.size() - 1) {printf(" ");}}return 0;
}

#include <cstdio>
#include <algorithm>
using namespace std;const int MAXN = 50;struct Node {int l, r;
} nodes[MAXN];int getHeight(int root) {if (root == -1) {return 0;}int leftHeight = getHeight(nodes[root].l);int rightHeight = getHeight(nodes[root].r);return max(leftHeight, rightHeight) + 1;
}int main() {int n;scanf("%d", &n);for (int i = 0; i < n; i++) {scanf("%d%d", &nodes[i].l, &nodes[i].r);}printf("%d", getHeight(0));return 0;
}

#include <cstdio>
#include <vector>
#include <queue>
using namespace std;const int MAXN = 50;struct Node {int l, r;
} nodes[MAXN];int layers[MAXN];void layerOrder(int root) {queue<int> q;q.push(root);int layer = 1;while (!q.empty()) {int cnt = q.size();for (int i = 0; i < cnt; i++) {int front = q.front();q.pop();layers[front] = layer;if (nodes[front].l != -1) {q.push(nodes[front].l);}if (nodes[front].r != -1) {q.push(nodes[front].r);}}layer++;}
}int main() {int n;scanf("%d", &n);for (int i = 0; i < n; i++) {scanf("%d%d", &nodes[i].l, &nodes[i].r);}layerOrder(0);for (int i = 0; i < n; i++) {printf("%d", layers[i]);if (i < n - 1) {printf(" ");}}return 0;
}

#include <cstdio>
#include <vector>
using namespace std;const int MAXN = 50;struct Node {int l, r;
} nodes[MAXN];vector<int> pre, in, post;int buildTree(int preL, int preR, int inL, int inR) {if (preL > preR) {return -1;}int root = pre[preL];int inIndexOfRoot;for (int i = inL; i <= inR; i++) {if (in[i] == root) {inIndexOfRoot = i;break;}}int leftCount = inIndexOfRoot - inL;nodes[root].l = buildTree(preL + 1, preL + leftCount, inL, inIndexOfRoot - 1);nodes[root].r = buildTree(preL + leftCount + 1, preR, inIndexOfRoot + 1, inR);return root;
}void postOrder(int root) {if (root == -1) {return;}postOrder(nodes[root].l);postOrder(nodes[root].r);post.push_back(root);
}int main() {int n, x;scanf("%d", &n);for (int i = 0; i < n; i++) {scanf("%d", &x);pre.push_back(x);}for (int i = 0; i < n; i++) {scanf("%d", &x);in.push_back(x);}int root = buildTree(0, n - 1, 0, n - 1);postOrder(root);for (int i = 0; i < (int)post.size(); i++) {printf("%d", post[i]);if (i < (int)post.size() - 1) {printf(" ");}}return 0;
}

#include <cstdio>
#include <vector>
using namespace std;const int MAXN = 50;struct Node {int l, r;
} nodes[MAXN];vector<int> pre, in, post;int buildTree(int postL, int postR, int inL, int inR) {if (postL > postR) {return -1;}int root = post[postR];int inIndexOfRoot;for (int i = inL; i <= inR; i++) {if (in[i] == root) {inIndexOfRoot = i;break;}}int leftCount = inIndexOfRoot - inL;nodes[root].l = buildTree(postL, postL + leftCount - 1, inL, inIndexOfRoot - 1);nodes[root].r = buildTree(postL + leftCount, postR - 1, inIndexOfRoot + 1, inR);return root;
}void preOrder(int root) {if (root == -1) {return;}pre.push_back(root);preOrder(nodes[root].l);preOrder(nodes[root].r);
}int main() {int n, x;scanf("%d", &n);for (int i = 0; i < n; i++) {scanf("%d", &x);post.push_back(x);}for (int i = 0; i < n; i++) {scanf("%d", &x);in.push_back(x);}int root = buildTree(0, n - 1, 0, n - 1);preOrder(root);for (int i = 0; i < (int)pre.size(); i++) {printf("%d", pre[i]);if (i < (int)pre.size() - 1) {printf(" ");}}return 0;
}

#include <cstdio>
#include <map>
#include <vector>
using namespace std;const int MAXN = 50;struct Node {int l, r;
} nodes[MAXN];vector<int> pre, in, layer;int buildTree(vector<int> layer, int inL, int inR) {if (layer.empty()) {return -1;}int root = layer[0];map<int, bool> isLeft;int inIndexOfRoot;for (int i = inL; i <= inR; i++) {if (in[i] == root) {inIndexOfRoot = i;break;} else {isLeft[in[i]] = true;}}vector<int> leftLayer, rightLayer;for (int i = 1; i < layer.size(); i++) {if (isLeft[layer[i]]) {leftLayer.push_back(layer[i]);} else {rightLayer.push_back(layer[i]);}}nodes[root].l = buildTree(leftLayer, inL, inIndexOfRoot - 1);nodes[root].r = buildTree(rightLayer, inIndexOfRoot + 1, inR);return root;
}void preOrder(int root) {if (root == -1) {return;}pre.push_back(root);preOrder(nodes[root].l);preOrder(nodes[root].r);
}int main() {int n, x;scanf("%d", &n);for (int i = 0; i < n; i++) {scanf("%d", &x);layer.push_back(x);}for (int i = 0; i < n; i++) {scanf("%d", &x);in.push_back(x);}int root = buildTree(layer, 0, n - 1);preOrder(root);for (int i = 0; i < (int)pre.size(); i++) {printf("%d", pre[i]);if (i < (int)pre.size() - 1) {printf(" ");}}return 0;
}

#include <cstdio>
#include <vector>
using namespace std;const int MAXN = 50;struct Node {int data;int l, r;
} nodes[MAXN];int treePathSum = 0;void getTreePathSum(int root, int nodePathSum) {if (root == -1) {return;}nodePathSum += nodes[root].data;if (nodes[root].l == -1 && nodes[root].r == -1) {treePathSum += nodePathSum;} else {getTreePathSum(nodes[root].l, nodePathSum);getTreePathSum(nodes[root].r, nodePathSum);}
}int main() {int n;scanf("%d", &n);for (int i = 0; i < n; i++) {scanf("%d", &nodes[i].data);}for (int i = 0; i < n; i++) {scanf("%d%d", &nodes[i].l, &nodes[i].r);}getTreePathSum(0, 0);printf("%d", treePathSum);return 0;
}

#include <cstdio>
#include <vector>
using namespace std;const int MAXN = 50;struct Node {int data;int l, r;
} nodes[MAXN];int treeWeightedPathLength = 0;void getTreeWeightedPathLength(int root, int nodePathLength) {if (root == -1) {return;}if (nodes[root].l == -1 && nodes[root].r == -1) {treeWeightedPathLength += nodes[root].data * nodePathLength;} else {nodePathLength++;getTreeWeightedPathLength(nodes[root].l, nodePathLength);getTreeWeightedPathLength(nodes[root].r, nodePathLength);}
}int main() {int n;scanf("%d", &n);for (int i = 0; i < n; i++) {scanf("%d", &nodes[i].data);}for (int i = 0; i < n; i++) {scanf("%d%d", &nodes[i].l, &nodes[i].r);}getTreeWeightedPathLength(0, 0);printf("%d", treeWeightedPathLength);return 0;
}

9.3树的遍历

#include <cstdio>
#include <vector>
using namespace std;const int MAXN = 50;struct Node {vector<int> children;
} nodes[MAXN];vector<int> pre;void preOrder(int root) {pre.push_back(root);for (int i = 0; i < nodes[root].children.size(); i++) {preOrder(nodes[root].children[i]);}
}int main() {int n, k, child;scanf("%d", &n);for (int i = 0; i < n; i++) {scanf("%d", &k);for (int j = 0; j < k; j++) {scanf("%d", &child);nodes[i].children.push_back(child);}}preOrder(0);for (int i = 0; i < pre.size(); i++) {printf("%d", pre[i]);if (i < (int)pre.size() - 1) {printf(" ");}}return 0;
}

#include <cstdio>
#include <vector>
using namespace std;const int MAXN = 50;struct Node {vector<int> children;
} nodes[MAXN];vector<int> post;void postOrder(int root) {for (int i = 0; i < nodes[root].children.size(); i++) {postOrder(nodes[root].children[i]);}post.push_back(root);
}int main() {int n, k, child;scanf("%d", &n);for (int i = 0; i < n; i++) {scanf("%d", &k);for (int j = 0; j < k; j++) {scanf("%d", &child);nodes[i].children.push_back(child);}}postOrder(0);for (int i = 0; i < post.size(); i++) {printf("%d", post[i]);if (i < (int)post.size() - 1) {printf(" ");}}return 0;
}

#include <cstdio>
#include <vector>
#include <queue>
using namespace std;const int MAXN = 50;struct Node {vector<int> children;
} nodes[MAXN];vector<int> layer;void layerOrder(int root) {queue<int> q;q.push(root);while (!q.empty()) {int front = q.front();q.pop();layer.push_back(front);for (int i = 0; i < nodes[front].children.size(); i++) {q.push(nodes[front].children[i]);}}
}int main() {int n, k, child;scanf("%d", &n);for (int i = 0; i < n; i++) {scanf("%d", &k);for (int j = 0; j < k; j++) {scanf("%d", &child);nodes[i].children.push_back(child);}}layerOrder(0);for (int i = 0; i < layer.size(); i++) {printf("%d", layer[i]);if (i < (int)layer.size() - 1) {printf(" ");}}return 0;
}

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;const int MAXN = 50;struct Node {int data;vector<int> children;
} nodes[MAXN];int treePathSum = 0;void getTreePathSum(int root, int nodePathSum) {nodePathSum += nodes[root].data;if (nodes[root].children.empty()) {treePathSum += nodePathSum;}for (int i = 0; i < nodes[root].children.size(); i++) {getTreePathSum(nodes[root].children[i], nodePathSum);}
}int main() {int n, k, child;scanf("%d", &n);for (int i = 0; i < n; i++) {scanf("%d", &nodes[i].data);}for (int i = 0; i < n; i++) {scanf("%d", &k);for (int j = 0; j < k; j++) {scanf("%d", &child);nodes[i].children.push_back(child);}}getTreePathSum(0, 0);printf("%d", treePathSum);return 0;
}

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;const int MAXN = 50;struct Node {int data;vector<int> children;
} nodes[MAXN];int treePathLength = 0;void getTreePathLength(int root, int edgeCount) {if (nodes[root].children.empty()) {treePathLength += nodes[root].data * edgeCount;}for (int i = 0; i < nodes[root].children.size(); i++) {getTreePathLength(nodes[root].children[i], edgeCount + 1);}
}int main() {int n, k, child;scanf("%d", &n);for (int i = 0; i < n; i++) {scanf("%d", &nodes[i].data);}for (int i = 0; i < n; i++) {scanf("%d", &k);for (int j = 0; j < k; j++) {scanf("%d", &child);nodes[i].children.push_back(child);}}getTreePathLength(0, 0);printf("%d", treePathLength);return 0;
}

9.4二叉查找树（BST）

#include <cstdio>
#include <vector>
using namespace std;const int MAXN = 50;struct Node {int data;int l, r;
} nodes[MAXN];int nodeCount = 0;int newNode(int data) {nodes[nodeCount].data = data;nodes[nodeCount].l = nodes[nodeCount].r = -1;return nodeCount++;
}int insert(int root, int data) {if (root == -1) {return newNode(data);}if (data < nodes[root].data) {nodes[root].l = insert(nodes[root].l, data);} else {nodes[root].r = insert(nodes[root].r, data);}return root;
}vector<int> pre;void preOrder(int root) {if (root == -1) {return;}pre.push_back(nodes[root].data);preOrder(nodes[root].l);preOrder(nodes[root].r);
}int main() {int n, data, root = -1;scanf("%d", &n);for (int i = 0; i < n; i++) {scanf("%d", &data);root = insert(root, data);}preOrder(root);for (int i = 0; i < (int)pre.size(); i++) {printf("%d", pre[i]);if (i < (int)pre.size() - 1) {printf(" ");}}return 0;
}

#include <cstdio>
#include <vector>
using namespace std;vector<int> in;bool isBST() {for (int i = 1; i < in.size(); i++) {if (in[i] <= in[i - 1]) {return false;}}return true;
}int main() {int n, x;scanf("%d", &n);for (int i = 0; i < n; i++) {scanf("%d", &x);in.push_back(x);}printf(isBST() ? "Yes" : "No");return 0;
}

9.5平衡二叉树（AVL树）

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;const int MAXN = 50;struct Node {int data;int height;int l, r;
} nodes[MAXN];int nodeCount = 0;int newNode(int data) {nodes[nodeCount].data = data;nodes[nodeCount].height = 1;nodes[nodeCount].l = nodes[nodeCount].r = -1;return nodeCount++;
}int getHeight(int root) {if (root == -1) {return 0;} else {return nodes[root].height;}
}void updateHeight(int root) {nodes[root].height = max(getHeight(nodes[root].l), getHeight(nodes[root].r)) + 1;
}int getBalanceFactor(int root) {return getHeight(nodes[root].l) - getHeight(nodes[root].r);
}int insert(int root, int data) {if (root == -1) {return newNode(data);}if (data < nodes[root].data) {nodes[root].l = insert(nodes[root].l, data);} else {nodes[root].r = insert(nodes[root].r, data);}updateHeight(root);return root;
}vector<int> balanceFactor;void inOrder(int root) {if (root == -1) {return;}inOrder(nodes[root].l);balanceFactor.push_back(getBalanceFactor(root));inOrder(nodes[root].r);
}int main() {int n, data, root = -1;scanf("%d", &n);for (int i = 0; i < n; i++) {scanf("%d", &data);root = insert(root, data);}inOrder(root);for (int i = 0; i < (int)balanceFactor.size(); i++) {printf("%d", balanceFactor[i]);if (i < (int)balanceFactor.size() - 1) {printf(" ");}}return 0;
}

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;const int MAXN = 50;struct Node {int data;int height;int l, r;
} nodes[MAXN];int nodeCount = 0;int newNode(int data) {nodes[nodeCount].data = data;nodes[nodeCount].height = 1;nodes[nodeCount].l = nodes[nodeCount].r = -1;return nodeCount++;
}int getHeight(int root) {if (root == -1) {return 0;} else {return nodes[root].height;}
}void updateHeight(int root) {nodes[root].height = max(getHeight(nodes[root].l), getHeight(nodes[root].r)) + 1;
}int getBalanceFactor(int root) {return getHeight(nodes[root].l) - getHeight(nodes[root].r);
}int insert(int root, int data) {if (root == -1) {return newNode(data);}if (data < nodes[root].data) {nodes[root].l = insert(nodes[root].l, data);} else {nodes[root].r = insert(nodes[root].r, data);}updateHeight(root);return root;
}bool isAVL(int root) {if (root == -1) {return true;}return isAVL(nodes[root].l) && isAVL(nodes[root].r) && abs(getBalanceFactor(root)) <= 1;
}int main() {int n, data, root = -1;scanf("%d", &n);for (int i = 0; i < n; i++) {scanf("%d", &data);root = insert(root, data);}printf(isAVL(root) ? "Yes" : "No");return 0;
}

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;const int MAXN = 50;struct Node {int data;int height;int l, r;
} nodes[MAXN];int nodeCount = 0;int newNode(int data) {nodes[nodeCount].data = data;nodes[nodeCount].height = 1;nodes[nodeCount].l = nodes[nodeCount].r = -1;return nodeCount++;
}int getHeight(int root) {if (root == -1) {return 0;} else {return nodes[root].height;}
}void updateHeight(int root) {nodes[root].height = max(getHeight(nodes[root].l), getHeight(nodes[root].r)) + 1;
}int getBalanceFactor(int root) {return getHeight(nodes[root].l) - getHeight(nodes[root].r);
}int L(int root) {int temp = nodes[root].r;nodes[root].r = nodes[temp].l;nodes[temp].l = root;updateHeight(root);updateHeight(temp);return temp;
}int R(int root) {int temp = nodes[root].l;nodes[root].l = nodes[temp].r;nodes[temp].r = root;updateHeight(root);updateHeight(temp);return temp;
}int insert(int root, int data) {if (root == -1) {return newNode(data);}if (data < nodes[root].data) {nodes[root].l = insert(nodes[root].l, data);updateHeight(root);if (getBalanceFactor(root) == 2) {if (getBalanceFactor(nodes[root].l) == 1) {root = R(root);} else if (getBalanceFactor(nodes[root].l) == -1) {nodes[root].l = L(nodes[root].l);root = R(root);}}} else {nodes[root].r = insert(nodes[root].r, data);updateHeight(root);if (getBalanceFactor(root) == -2) {if (getBalanceFactor(nodes[root].r) == -1) {root = L(root);} else if (getBalanceFactor(nodes[root].r) == 1) {nodes[root].r = R(nodes[root].r);root = L(root);}}}return root;
}vector<int> pre;void preOrder(int root) {if (root == -1) {return;}pre.push_back(nodes[root].data);preOrder(nodes[root].l);preOrder(nodes[root].r);
}int main() {int n, data, root = -1;scanf("%d", &n);for (int i = 0; i < n; i++) {scanf("%d", &data);root = insert(root, data);}preOrder(root);for (int i = 0; i < (int)pre.size(); i++) {printf("%d", pre[i]);if (i < (int)pre.size() - 1) {printf(" ");}}return 0;
}

9.6并查集

#include <cstdio>
#include <cstring>const int MAXN = 100;
int father[MAXN];int findFather(int x) {int xCopy = x;while (father[x] != x) {x = father[x];}int root = x;x = xCopy;while (father[x] != x) {int fatherX = father[x];father[x] = root;x = fatherX;}return root;
}void unionSet(int a, int b) {int faA = findFather(a);int faB = findFather(b);if (faA != faB) {father[faA] = faB;}
}void init(int n) {for (int i = 0; i < n; i++) {father[i] = i;}
}int main() {int n, m, a, b;scanf("%d%d", &n, &m);init(n);for (int i = 0; i < m; i++) {scanf("%d%d", &a, &b);unionSet(a - 1, b - 1);}int classCount = 0;for (int i = 0; i < n; i++) {if (father[i] == i) {classCount++;}}printf("%d", classCount);return 0;
}

#include <cstdio>
#include <cstring>const int MAXN = 100;
int father[MAXN];int findFather(int x) {int xCopy = x;while (father[x] != x) {x = father[x];}int root = x;x = xCopy;while (father[x] != x) {int fatherX = father[x];father[x] = root;x = fatherX;}return root;
}void unionSet(int a, int b) {int faA = findFather(a);int faB = findFather(b);if (faA != faB) {father[faA] = faB;}
}void init(int n) {for (int i = 0; i < n; i++) {father[i] = i;}
}int main() {int n, m, a, b;scanf("%d%d", &n, &m);init(n);for (int i = 0; i < m; i++) {scanf("%d%d", &a, &b);unionSet(a - 1, b - 1);}bool linked = true;for (int i = 1; i < n; i++) {if (findFather(i) != findFather(0)) {linked = false;}}printf(linked ? "Yes" : "No");return 0;
}

#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;const int MAXN = 100;
int father[MAXN];
int score[MAXN];vector<int> classes;int findFather(int x) {int xCopy = x;while (father[x] != x) {x = father[x];}int root = x;x = xCopy;while (father[x] != x) {int fatherX = father[x];father[x] = root;x = fatherX;}return root;
}void unionSet(int a, int b) {int faA = findFather(a);int faB = findFather(b);if (faA != faB) {if (score[faA] < score[faB]) {father[faA] = faB;} else {father[faB] = faA;}}
}void init(int n) {for (int i = 0; i < n; i++) {father[i] = i;}
}int main() {int n, m, a, b;scanf("%d%d", &n, &m);init(n);for (int i = 0; i < n; i++) {scanf("%d", &score[i]);}for (int i = 0; i < m; i++) {scanf("%d%d", &a, &b);unionSet(a - 1, b - 1);}for (int i = 0; i < n; i++) {if (findFather(i) == i) {classes.push_back(score[i]);}}sort(classes.rbegin(), classes.rend());printf("%d\n", (int)classes.size());for (int i = 0; i < classes.size(); i++) {printf("%d", classes[i]);if (i < (int)classes.size() - 1) {printf(" ");}}return 0;
}

9.7堆

#include <cstdio>
#include <algorithm>
using namespace std;const int MAXN = 1000 + 1;
int heap[MAXN];void downAdjust(int low, int high) {int i = low, j = i * 2;while (j <= high) {if (j + 1 <= high && heap[j + 1] > heap[j]) {j = j + 1;}if (heap[j] > heap[i]) {swap(heap[j], heap[i]);i = j;j = i * 2;} else {break;}}
}void createHeap(int n) {for (int i = n / 2; i >= 1; i--) {downAdjust(i, n);}
}int main() {int n;scanf("%d", &n);for (int i = 1; i <= n; i++) {scanf("%d", &heap[i]);}createHeap(n);for (int i = 1; i <= n; i++) {printf("%d", heap[i]);if (i < n) {printf(" ");}}return 0;
}

#include <cstdio>
#include <algorithm>
using namespace std;const int MAXN = 1000 + 1;
int heap[MAXN];void downAdjust(int low, int high) {int i = low, j = i * 2;while (j <= high) {if (j + 1 <= high && heap[j + 1] > heap[j]) {j = j + 1;}if (heap[j] > heap[i]) {swap(heap[j], heap[i]);i = j;j = i * 2;} else {break;}}
}void createHeap(int n) {for (int i = n / 2; i >= 1; i--) {downAdjust(i, n);}
}int deleteTop(int n) {if (n > 0) {heap[1] = heap[n--];downAdjust(1, n);}return n;
}int main() {int n;scanf("%d", &n);for (int i = 1; i <= n; i++) {scanf("%d", &heap[i]);}createHeap(n);n = deleteTop(n);for (int i = 1; i <= n; i++) {printf("%d", heap[i]);if (i < n) {printf(" ");}}return 0;
}

#include <cstdio>
#include <algorithm>
using namespace std;const int MAXN = 50 + 1;
int heap[MAXN];void downAdjust(int low, int high) {int i = low, j = i * 2;while (j <= high) {if (j + 1 <= high && heap[j + 1] > heap[j]) {j = j + 1;}if (heap[j] > heap[i]) {swap(heap[j], heap[i]);i = j;j = i * 2;} else {break;}}
}void createHeap(int n) {for (int i = n / 2; i >= 1; i--) {downAdjust(i, n);}
}void heapSort(int n) {createHeap(n);for (int i = n; i > 1; i--) {swap(heap[i], heap[1]);downAdjust(1, i - 1);}
}int main() {int n;scanf("%d", &n);for (int i = 1; i <= n; i++) {scanf("%d", &heap[i]);}heapSort(n);for (int i = 1; i <= n; i++) {printf("%d", heap[i]);if (i < n) {printf(" ");}}return 0;
}

9.8哈夫曼树

#include <iostream>
#include <vector>
#include <queue>using namespace std;int minCostToMergeFruits(vector<int>& fruits) {// 使用优先队列（最小堆）来处理priority_queue<int, vector<int>, greater<int>> minHeap(fruits.begin(), fruits.end());int totalCost = 0;// 当堆中还有超过一个元素时，进行合并操作while (minHeap.size() > 1) {// 取出最小的两个果堆int first = minHeap.top();minHeap.pop();int second = minHeap.top();minHeap.pop();// 合并这两个果堆int mergedCost = first + second;totalCost += mergedCost;// 将新的合并后的果堆放回堆中minHeap.push(mergedCost);}return totalCost;
}int main() {int n;cin >> n;vector<int> fruits(n);for (int i = 0; i < n; ++i) {cin >> fruits[i];}int result = minCostToMergeFruits(fruits);cout << result << endl;return 0;
}

#include <cstdio>
#include <queue>
using namespace std;priority_queue<int, vector<int>, greater<int> > pq;int main() {int n, weight;scanf("%d", &n);for (int i = 0; i < n; i++) {scanf("%d", &weight);pq.push(weight);}int ans = 0;while (pq.size() > 1) {int top1 = pq.top();pq.pop();int top2 = pq.top();pq.pop();pq.push(top1 + top2);ans += top1 + top2;}printf("%d", ans);return 0;
}

#include <iostream>
#include <string>
#include <queue>
using namespace std;const int MAXC = 26;
int charCnt[MAXC] = {0};priority_queue<int, vector<int>, greater<int> > pq;int main() {string s;cin >> s;for (int i = 0; i < s.length(); i++) {charCnt[s[i] - 'A']++;}for (int i = 0; i < MAXC; i++) {if (charCnt[i] > 0) {pq.push(charCnt[i]);}}int ans = 0;while (pq.size() > 1) {int top1 = pq.top();pq.pop();int top2 = pq.top();pq.pop();pq.push(top1 + top2);ans += top1 + top2;}printf("%d", ans);return 0;
}