1. 二叉堆
二叉堆是一种常用的数据结构，可以用来进行优先队列的操作。同时，它也可以实现堆排序。二叉堆是一种完全二叉树，分为大根堆和小根堆。
1.1 大根堆
大根堆的每个节点都比它的子节点大。例如，下图就是一个大根堆。
100
/ \
80 90
/ \ / \
70 60 30 40
大根堆的实现方式可以采用数组来进行存储。将父节点的下标记做i，则其左子节点的下标为2*i，右子节点的下标为2*i+1。
当我们向大根堆中插入一个数时，我们需要将该数放置在堆的最后一个位置，并且不断和其父节点进行比较、交换，以维持堆的性质。详细地说，插入的过程如下所示：
将元素插入之后，如果其值比父节点大，则交换元素和父节点。
不断重复以上步骤，直到元素不再比父节点大或者已经到达根节点。
下面是大根堆的插入代码：
void maxHeapify(int arr[], int i, int size) {
int l = 2*i+1;
int r = 2*i+2;
int largest = i;
if (l < size && arr[l] > arr[largest])
largest=l;
if (r < size && arr[r] > arr[largest])
largest=r;
if (largest != i) {
swap(arr[i], arr[largest]);
maxHeapify(arr, largest, size);
}
}
void insert(int arr[], int& size, int val) {
arr[size] = val;
int i = size;
while (i > 0 && arr[(i-1)/2] < arr[i]) {
swap(arr[i], arr[(i-1)/2]);
i = (i-1)/2;
}
size++;
}
当我们需要删除堆中的元素时，我们需要将堆的最后一个元素放置到根节点处，并且对该节点进行下滤以保证堆的性质。详细地说，删除的过程如下所示：
将最后一个元素放置到根节点处。
将该节点不断和其子节点进行比较，如果某个子节点比其大，则交换元素。
不断重复以上步骤，直到节点没有子节点或者其子节点都比其小。
下面是大根堆的删除代码：
void deleteMax(int arr[], int& size) {
size--;
swap(arr[0], arr[size]);
maxHeapify(arr, 0, size);
}
1.2 小根堆
小根堆的每个节点都比它的子节点小。例如，下图就是一个小根堆。
10
/ \
20 30
/ \ / \
40 50 60 70
小根堆可以采用与大根堆类似的方式进行实现，只需要对插入和删除进行微调即可。
下面是小根堆的插入代码：
void minHeapify(int arr[], int i, int size) {
int l = 2*i+1;
int r = 2*i+2;
int smallest = i;
if (l < size && arr[l] < arr[smallest])
smallest=l;
if (r < size && arr[r] < arr[smallest])
smallest=r;
if (smallest != i) {
swap(arr[i], arr[smallest]);
minHeapify(arr, smallest, size);
}
}
void insert(int arr[], int& size, int val) {
arr[size] = val;
int i = size;
while (i > 0 && arr[(i-1)/2] > arr[i]) {
swap(arr[i], arr[(i-1)/2]);
i = (i-1)/2;
}
size++;
}
下面是小根堆的删除代码：
void deleteMin(int arr[], int& size) {
size--;
swap(arr[0], arr[size]);
minHeapify(arr, 0, size);
}
2. 二叉搜索树
二叉搜索树是一种最常用的数据结构之一。它是一棵二叉树，其中每个节点都包含一个关键字，且每个节点的左子树中的所有节点的关键字都小于该节点的关键字，每个节点的右子树中的所有节点的关键字都大于该节点的关键字。
下面是一棵二叉搜索树的例子：
8
/ \
3 10
/ \ \
1 6 14
/ \ /
4 7 13
二叉搜索树可以用来进行快速查找、插入、删除等操作。下面介绍二叉搜索树的查找、插入、删除操作。
2.1 查找
查找一个元素在二叉搜索树中的位置可以采用递归的方式进行实现。如果需要查找的节点值小于当前节点的值，则递归查找当前节点的左子树。反之，如果需要查找的节点值大于当前节点的值，则递归查找当前节点的右子树。如果查找成功，则返回该节点；如果查找失败，则返回空值。
下面是二叉搜索树的查找代码：
TreeNode* search(TreeNode* root, int val) {
if (root == NULL || root->val == val)
return root;
if (root->val > val)
return search(root->left, val);
else
return search(root->right, val);
}
2.2 插入
在二叉搜索树中插入一个节点可以采用递归的方式进行实现。如果需要插入的节点值小于当前节点的值，则递归插入当前节点的左子树。反之，如果需要插入的节点值大于当前节点的值，则递归插入当前节点的右子树。如果查找失败，则创建一个新的节点，并且将其插入到该节点的左子树或右子树中。
下面是二叉搜索树的插入代码：
TreeNode* insert(TreeNode* root, int val) {
if (root == NULL)
return new TreeNode(val);
if (root->val > val)
root->left = insert(root->left, val);
else
root->right = insert(root->right, val);
return root;
}
2.3 删除
在二叉搜索树中删除一个节点需要考虑到多种情况。如果需要删除的节点是叶子节点，则直接删除该节点即可。如果需要删除的节点只有一个子节点，则将该节点的子节点代替该节点即可。如果需要删除的节点有两个子节点，则需要找到该节点的后继节点（即比该节点大的最小节点），将该节点的值替换为后继节点的值，并且递归删除后继节点。
下面是二叉搜索树的删除代码：
TreeNode* deleteNode(TreeNode* root, int key) {
if (root == NULL)
return NULL;
if (root->val > key) {
root->left = deleteNode(root->left, key);
return root;
}
if (root->val < key) {
root->right = deleteNode(root->right, key);
return root;
}
if (root->left == NULL) {
TreeNode* right = root->right;
delete root;
return right;
}
if (root->right == NULL) {
TreeNode* left = root->left;
delete root;
return left;
}
TreeNode* successor = getSuccessor(root);
root->val = successor->val;
root->right = deleteNode(root->right, successor->val);
return root;
}
TreeNode* getSuccessor(TreeNode* root) {
root = root->right;
while (root != NULL && root->left != NULL)
root = root->left;
return root;
}
3. 总结
本文介绍了C++中的二叉堆和二叉搜索树。二叉堆是一种常用的数据结构，可以用来进行优先队列的操作。同时，它也可以实现堆排序。二叉搜索树是一种最常用的数据结构之一。它是一棵二叉树，其中每个节点都包含一个关键字，且每个节点的左子树中的所有节点的关键字都小于该节点的关键字，每个节点的右子树中的所有节点的关键字都大于该节点的关键字。二叉搜索树可以用来进行快速查找、插入、删除等操作。
总之，C++中的二叉堆和二叉搜索树是非常重要的数据结构。它们具有广泛的应用，对于每个C++程序员来说都是必备的知识。