关于堆(max-heap和min heap)

Question

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

Answer 1

这并不重要。max-heap中的节点必须具有较低的子节点，而min-heap中的节点必须具有较大的子节点。这些是唯一的要求。

Answer 2

最大堆属性：

1. 根是最大元素。O(1)搜索最大element.
2. Children的时间总是小于任何子树的根。(左和右children)
3. Minimum元素在叶元素中的某个地方没有条件，即寻找最小元素需要O(n/2) == O(n)时间。

Min-Heap属性：

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

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

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