算法中使用的二进制堆和二进制搜索树 - 傻瓜

特殊类型的树结构是 二元堆 ，它将每个节点元素置于特定的顺序。搜索树使您能够快速查找数据。获取数据项目，将它们按照排序顺序排列在树中，然后搜索该树是查找信息的更快方法之一。

在二进制堆中，根节点始终包含最小值。在查看分支时，您会发现上层分支总是比下层分支和分支小。其效果是保持树的平衡和可预测的顺序，使搜索变得非常有效。成本是保持树木平衡。

<！ --1 - >

在应用程序所做的所有任务中，搜索更耗时，也是最需要的。即使添加数据（并在稍后进行排序）确实需要一定的时间，创建和维护数据集的好处也来自于使用它来执行有用的工作，这意味着要搜索重要的信息。因此，有时您可能会使用效率较低的CRUD功能，甚至是不太理想的排序例程，但搜索必须尽可能高效地进行。唯一的问题是，没有一个搜索能够以绝对有效的方式执行每个任务，所以你必须根据你期望做的搜索例程的一部分权衡你的选项。

<！两种更高效的搜索方法涉及使用二叉搜索树（BST）和二进制堆。这两种搜索技术都依赖于树形结构来保存用于访问数据元素的密钥。但是，这两种方法的安排是不同的，这就是为什么一个人在执行某些任务时有优势。这张图显示了一个BST的安排。

使用BST时按键的排列。

请注意，按键的顺序是左边出现较少数字，右边出现较大数字。根节点包含一个位于键范围中间的值，给BST一个易于理解的均衡方法来存储键。将此安排与此处显示的二进制堆对比。

使用二进制堆时的键排列。

每个级别都包含小于上一级别的值，并且根目录包含树的最大键值。另外，在这种特殊情况下，较小的值出现在左侧，而较大的值出现在右侧（尽管这个顺序没有严格执行）。该图实际上描述了一个

二进制最大堆。 还可以创建一个 二进制分钟堆 ，其中根包含最低的键值，每个级别的值都会更高，最高值将显示为树叶的一部分。如前所述，BST在用于执行搜索时比二进制堆有一些优点。以下列表提供了这些优点的一些亮点： 搜索元素需要O（log n）时间，与二进制堆的O（n）时间形成对比。

按顺序打印元素只需要O（log n）时间，与二进制堆的O（n log n）时间形成对比。找到地板和天花板需要O（log n）时间。

• 定位第K个最小/最大元素需要O（log n）时间树正确配置。
• 这些时间是否重要取决于您的应用程序。在花费更多时间搜索和减少构建树的情况下，BST趋向于最佳工作。二进制堆往往在密钥经常变化的动态情况下效果最好。二进制堆也提供了一些优点，如下面的列表所述：
• 创建所需的结构所需的资源更少，因为二进制堆依赖于数组，因此它们也缓存更友好。
• 构建二进制堆需要O（n）个时间，与BST相比，这需要O（n log n）时间。

使用指针来实现树是没有必要的。依靠二进制堆的变化（例如斐波那契堆）提供了诸如增加和减少O（1）时间的关键时间的优点。