构建有效的堆
我只需要验证一下我的做法是否正确。我检查了 wiki 上的堆排序，但在动画中似乎构建堆时会将数字插入节点并按顺序对其进行排序。
问题要求“用这些元素绘制一个有效的堆.. {7, 12, 1, 3, 22, 5, 11} 作为一棵树”
我已经在几个例子中尝试过了，看来我应该布局首先节点，然后重新排序节点，而不是按照我的顺序进行排序。我这样做的方式正确吗？
例如，将元素放入节点
7
12 1
3 22 5 11
排序从此处开始：交换 1 和 7
7
12 1
3 22 5 11
交换 3 和 12
1
12 7
3 22 5 11
交换 5 和 7
1
3 7
12 22 5 11
完成。
1
3 5
12 22 7 11
其实这是不对的。
给出的答案是
1
7 3
12 22 5 11
如果我首先从左侧开始对堆重新排序（从 3 开始），那么我会得到正确的答案。
I just need some verification on whether or not I'm doing this correctly. I checked the wiki for a heapsort, but it seems in the animation to build the heap it inserts the numbers into the nodes and orders it as it goes.
The question asks to "Draw a valid heap with these elements.. {7, 12, 1, 3, 22, 5, 11} as a tree"
I've tried it on a few examples, and it seems I should layout the nodes first then reorder the nodes instead of ordering it as I go. Is the way I'm doing it correct?
For example, putting elements into the nodes
7
12 1
3 22 5 11
Ordering begins here: swap 1 and 7
7
12 1
3 22 5 11
Swap 3 and 12
1
12 7
3 22 5 11
Swap 5 and 7
1
3 7
12 22 5 11
done.
1
3 5
12 22 7 11
Actually that's not right.
The answer given is
1
7 3
12 22 5 11
If I begin to re-order the heap from the left side first (beginning with 3) then I get the right answer.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
实际上，堆数据结构只有一个属性，可以定义如下：“在堆T中，对于除根之外的每个节点v，存储在v处的键大于或等于存储在v的父节点处的键”。
因此，基于元素（7、12、1、3、22、5、11）的堆有多种正确表示。对于这些元素，我应用了“插入和排序”算法，结果给出了另一个版本：
Actually, the heap data structure as only one property, which can be defined as follows: "In a heap T, for every node v other than the root, the key stored at v is greater than or equal to the key stored at v's parent."
So there are many right representations of the heap based on elements (7, 12, 1, 3, 22, 5, 11). With these elements I applied an "insert-and-sort" algorithm and the result gives yet another version: