二叉排序树与堆的区别

定义与结构

在二叉排序树中，每个结点的值均大于其左子树上所有结点的值，小于其右子树上所有结点的值。对二叉排序树进行中序遍历得到一个有序序列。它是结点之间满足一定次序关系的二叉树。

堆是一个完全二叉树，并且每个结点的值都大于或等于其左右孩子结点的值（以大根堆为例）。它是结点之间满足一定次序关系的完全二叉树。

深度比较

具有 n 个结点的二叉排序树，其深度取决于给定集合的初始排列顺序：

• 最好情况下深度为 log n；
• 最坏情况下深度为 n。

具有 n 个结点的堆，其深度即为堆所对应的完全二叉树的深度 log n。

结点关系

• 二叉排序树：某结点的右孩子结点的值一定大于该结点的左孩子结点的值。
• 堆：仅限定某结点的值大于（或小于）其左右孩子结点的值，没有限定左右孩子结点之间的大小关系。

最小值与最大值位置

• 二叉排序树：
  • 最小值结点是最左下结点，其左指针为空；
  • 最大值结点是最右下结点，其右指针为空。
• 大根堆：
  • 最小值结点位于某个叶子结点；
  • 最大值结点是大根堆的堆顶（即根结点）。

应用场景与复杂度

• 二叉排序树：面向查找操作设计。查找一个结点的平均时间复杂度是 O(log n)。
• 堆：面向排序操作设计。不是面向查找操作的，查找一个结点需要进行遍历，平均时间复杂度是 O(n)。