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

Question

我有一个问题，在堆数据结构中，左孩子可以比其所在级别的右孩子多吗？我的意思是，考虑这三个数字 9、5、8，我想创建一个最大堆数据结构，因此根将为 9，并且 8 是其左子节点，5 是其右子节点，这是真的吗？请帮助我，谢谢

Answer 1

最大堆属性：

1. 根是最大元素。搜索最大元素的时间为 O(1)。
2. 子树总是小于任何子树的根。（左右子树之间没有条件）
3. 最小元素位于叶子元素中的某个位置，即需要 O(n/2) == O(n) 时间来找到最小元素。

最小堆属性：

1. 根是最小元素。搜索 mim 元素的时间为 O(1)。
2. 子树总是大于任何子树的根。（左子树和右子树之间没有条件）
3. 最大元素位于叶子元素中的某个位置，即找到最大元素需要 O(n/2) == O(n) 时间。

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

对于搜索，我们总是可以使用二叉搜索树（BST），它在 O(h) 时间内完成同样的事情。在最好的情况下，如果 BS 树是平衡的，它将在 O(logn) 中进行搜索。