C++中的二叉堆和二叉搜索树

在C++编程中，二叉堆和二叉搜索树是两种常用的数据结构，它们具有相似之处，但是也有着不同点。本文将分别介绍二叉堆和二叉搜索树的概念、基本操作及其应用场景。

一、 二叉堆

1.1 概念

二叉堆是一种完全二叉树，满足以下两种性质：

1.1.1 堆序性

堆序性指在一个二叉堆中，每个节点的值都不大于（或不小于）其父节点的值。这里以最大堆为例，即根节点的值是整个树中最大的值，而所有子节点的值都小于等于根节点的值。

1.1.2 完全二叉树性质

除了最底层之外，其他层都必须填满，且所有节点都必须向左对齐。

这里以如下的数组来表示一个最大堆：

[ 16, 14, 10, 8, 7, 9, 3, 2, 4 , 1 ]

则其对应的堆如下图所示：

16

/
14 10
/ /
8 7 9 3
/
2 4

1

1.2 基本操作

1.2.1 插入操作

在一个二叉堆中插入一个新元素的操作，采用“上滤”（sift up）的方法进行调整：

• 将新元素插入到堆底最左边的空位；
• 将新元素和它的父节点进行比较，如果新元素的值比其父节点大，则交换两者的位置，重复此过程直到新元素不再比其父节点大，或到达堆顶。

1.2.2 删除操作

在一个二叉堆中删除堆顶元素的操作，采用“下滤”（sift down）的方法进行调整：

• 将堆顶元素和堆底最右边的元素互换；
• 删除原来的堆顶元素；
• 将新的堆顶元素逐层与其子节点进行比较，如果它的值小于子节点中的最大值，则将它与子节点中的最大值进行交换，重复此过程直到满足堆序性。

1.3 应用场景

二叉堆常用来实现优先队列，以及基于堆的排序算法，如堆排序、topK问题等。

二、 二叉搜索树

2.1 概念

二叉搜索树（Binary Search Tree，BST）是一种有序树，满足以下性质：

2.1.1 左子树上所有节点的值均小于它的根节点的值。

2.1.2 右子树上所有节点的值均大于它的根节点的值。

2.1.3 左、右子树也分别为二叉搜索树。

以如下树为例：

    6
  /   
 2     7

/
1 4 9

   /    /
  3   5 8

则它是一棵二叉搜索树。

2.2 基本操作

2.2.1 查找操作

在二叉搜索树中查找一个节点的操作，其实质就是不断地比较要查找的节点值与当前节点值的大小，并沿着左/右子树递归查找。

2.2.2 插入操作

在二叉搜索树中插入一个新节点的操作，需要从根节点开始进行比较，并找到其应该插入的位置，插入后需要满足二叉搜索树的性质。

2.2.3 删除操作

在二叉搜索树中删除一个节点的操作，分三种情况：

• 要删除的节点是叶子节点，直接删除即可；
• 要删除的节点只有一个子节点时，用它的子节点替换该节点；
• 要删除的节点有两个子节点时，用该节点右子树的最小节点代替该节点，并将该节点右子树的最小节点删除。

2.3 应用场景

二叉搜索树常用来实现字典、符号表等具有查找和插入操作的场景，其中的查找性能与数据的分布情况有关。

三、 二叉堆和二叉搜索树的比较

3.1 相似之处

二叉堆和二叉搜索树均是二叉树，具有一些相同的性质：

• 根节点的初始位置均可以是任意节点；
• 都可以用来实现优先队列；
• 插入和删除的时间复杂度均为O(logn)。

3.2 不同之处

二叉堆和二叉搜索树之间也有一些明显的不同点：

3.2.1 数据分布

在二叉堆中，元素没有任何规律地分布在各个节点中，只需保证每个节点都满足堆序性即可；而在二叉搜索树中，元素的大小有特定的排序规则，即满足左小右大的性质。

3.2.2 最小/最大值的访问

在二叉堆中，可以O(1)地访问到最大/最小值，即在根节点中得到，但是访问其他元素的时间复杂度为O(logn)；而在二叉搜索树中，查找最小/最大值需要遍历子树，时间复杂度也为O(logn)。

3.2.3 删除和插入操作

在二叉堆中，每次删除和插入操作都必须遵循堆序性，即O(logn)的时间复杂度；而在二叉搜索树中，查找一个节点和插入一个新节点的时间复杂度与树的高度相关，因此最坏情况下可能需要O(n)的时间复杂度。

3.3 选型建议

在选择二叉堆和二叉搜索树时，需要根据应用场景的具体情况进行选择。

如果需要快速地获取最小/最大值，并且对元素的大小没有特殊要求，可以优先选择二叉堆。

如果需要快速地插入/删除元素，并且需要元素的大小有一定的排序规律，可以考虑选择二叉搜索树。

四、 结论

综上所述，二叉堆和二叉搜索树都是比较重要的数据结构，在不同的场景下有着各自的优缺点。了解二叉堆和二叉搜索树的概念、基本操作及其应用场景对于编写高效的程序具有重要的意义。