如何创建堆？
假设我有一个如下所示的堆：
77
/ \
/ \
50 60
/ \ / \
22 30 44 55
现在，我想将另一个项目 55 插入到这个堆中。
如何做到这一点？
选项 1.
77
/ \
/ \
55 60
/ \ / \
50 30 44 55
/
22
选项 2.
77
/ \
/ \
55 60
/ \ / \
22 50 44 55
\
30
选项 3.
77
/ \
/ \
50 60
/ \ / \
22 30 55 55
/
44
哪一个是正确的步骤？为什么？请解释一下。
Suppose I have a Heap Like the following:
77
/ \
/ \
50 60
/ \ / \
22 30 44 55
Now, I want to insert another item 55 into this Heap.
How to do this?
Option 1.
77
/ \
/ \
55 60
/ \ / \
50 30 44 55
/
22
Option 2.
77
/ \
/ \
55 60
/ \ / \
22 50 44 55
\
30
Option 3.
77
/ \
/ \
50 60
/ \ / \
22 30 55 55
/
44
Which is the correct step? And Why? Please explain.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
选项 1 是正确的..
因为我们从最左边的节点开始添加子节点，如果父节点低于新添加的子节点，那么我们将替换它们。如此下去，直到孩子得到比它更有价值的父母。
您的初始树
现在根据最左侧的规则添加 55。
但你看到 22 低于 55，所以将其替换。
现在 55 已经成为 50 的孩子，仍然低于 55，所以也替换它们。
现在不能再排序了，因为 77 大于 55 ...
所以你的选项1是正确的。
在这里您可以详细查看堆排序示例。
此链接指出
堆是一种特殊的基于树的数据结构，它满足堆属性：如果 B 是 A 的子节点，则 key(A) ≥ key(B)。这意味着具有最大键的元素始终位于根节点中，因此这样的堆有时称为最大堆。 （或者，如果比较相反，则最小元素始终位于根节点中，这会产生最小堆。）对于堆中每个节点有多少个子节点没有限制，尽管实际上每个节点都有最多两个。
祝你好运
Option 1 is right..
Because we start adding child from the most left node and if the parent is lower than the newly added child than we replace them. And like so will go on until the child got the parent having value greater than it.
Your initial tree is
Now adding 55 according to the rule on most left side.
But you see 22 is lower than 55 so replaced it.
Now 55 has become the child of 50 which is still lower than 55 so replace them too.
Now it cant be sorted more because 77 is greater than 55 ...
SO your option 1 is right.
here you can see heap sort example in detail..
This link states
a heap is a specialized tree-based data structure that satisfies the heap property: if B is a child node of A, then key(A) ≥ key(B). This implies that an element with the greatest key is always in the root node, and so such a heap is sometimes called a max-heap. (Alternatively, if the comparison is reversed, the smallest element is always in the root node, which results in a min-heap.) There is no restriction as to how many children each node has in a heap, although in practice each node has at most two.
Good Luck
选项1，根据定义二叉堆的形状是完全二叉树。另外两个不是完全二叉树。
请参阅http://en.wikipedia.org/wiki/Binary_heap
Option 1, by definition binary heap's shape is a complete binary tree. The other 2 are not complete binary trees.
See http://en.wikipedia.org/wiki/Binary_heap
正确选项是1.
为什么？
请记住，堆的一个属性是完整的二叉树，即它们的所有级别（可能除了最后一个级别）都被完全填充，并且所有节点都尽可能远离......维基百科？
在选项2和3中，元素没有插入到尽可能靠左的位置，因此完全二叉树的性质被破坏。
关于元素的最终位置，是将插入的元素（儿子）与其直接祖先（父亲）交换，而儿子小于父亲。
The correct option is 1.
Why?
Remember than one property of a heap is to be a complete binary tree, i.e. all of their levels, except possibly the last, is completely filled, and all nodes are as far left as possible...wikipedia?
In options 2 and 3 the element is not inserted as far left as possible, and, therefore the property of complete binary tree is broken.
With respect to the final position of the element is by exchanging the inserted element(son) with their direct ancestor(father) while the son is less than the father.