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

Question

我有这个问题，在堆数据结构中，左孩子在自己的级别上可以多于右孩子吗？我的意思是考虑这三个数字 9,5,8 并且我想创建一个最大堆数据结构，因此根将是 9，并且 8 是它的左孩子而 5 是它的右孩子是真的吗？请帮帮我谢谢

Answer 1

最大堆属性：

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

最小堆属性：

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

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

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

Answer 2

那没关系。最大堆中的节点必须具有较小的子节点，而最小堆中的节点必须具有较大的子节点。这些是唯一的要求。