关于堆（最大堆和最小堆）

我有这样一个问题，在堆数据结构中，左边的孩子可能不止是一个正确的孩子在自己的水平？我的意思是考虑这三个数字9,5,8，我想创建一个最大堆数据结构，这样根就会是9，它是真的，8是它的左边的孩子，5是它的正确孩子？请帮助我谢谢关于堆（最大堆和最小堆）

来源

2010-06-25 user355002

这没关系。 max-heap中的节点必须具有较低的子节点，并且min-heap中的节点必须具有较大的子节点。这些是唯一的要求。

来源

2010-06-25 07:11:18

因此，我们如何设置父项的左右子项没有规则？因为堆几乎是完整的二叉树，我认为这是二叉树中的一条规则，让孩子应该少于正确的孩子！我认为对于我上面的例子，我应该写“root：9”和“leftChild：5”和“rightChild：8”，不是吗？ – user355002 2010-06-25 07:16:23

你通常会建立一个最大堆的方式是从数组的中间开始第一个元素，并通过交换节点递归地让每个节点在树中向下筛选。这可以在O（n）时间完成。它不是一个二叉搜索树，所以兄弟节点之间没有特别的关系，除了它们比它们的父节点更小（或者在min-heap的情况下更大）之外。 – 2010-06-25 07:25:34

aha，如果我们想在这个数据结构中搜索一个关键字，我们不需要将它作为一个二叉搜索树？ – user355002 2010-06-25 07:45:20

最大堆性能：

Root是最大元素。 O（1）时间来搜索最大元素。
儿童总是比任何子树的根小。（有左和右孩子之间没有条件）
最小元件位于簧片元件某处，即为O（n/2）==Ô （n）需要时间来找到最小元素。

最小堆性能：

根是最小的元素。 O（1）搜索mim元素的时间。
儿童总是比任何子树的根值。（有左和右孩子之间没有条件）
最大元件位于簧片元件某处，即为O（n/2）==Ô （n）需要时间才能找到最大元素。

因此，堆不适合搜索，但它用于排序元素数组，因为搜索需要线性O（n）时间。

对于搜索，我们总是可以选择在O（h）时间执行相同操作的二进制搜索树（BST）。在最好的情况下，如果BS树是平衡的，它将在O（logn）中进行搜索。

来源

2015-03-31 00:35:25 CODError

关于堆（最大堆和最小堆）

回答

相关问题