堆中最大的项目
堆中最大的项必须出现在位置 1，第二大的项必须出现在位置 1 位于位置 2 或位置 3。给出大小为 31 的堆中的位置列表，其中 第 k 个最大的 (i) 可以出现，而 (ii) 不能出现，因为 k=2, 3, 4（假设值为 是独特的）。
我正试图在期中考试中研究这个问题，但现在已经凌晨 3 点了，我在书中遇到了这个问题，因为它没有提供解决方案。任何帮助将不胜感激。
The largest item in a heap must appear in position 1, and the second largest must
be in position 2 or position 3. Give the list of positions in a heap of size 31 where the
kth largest (i) can appear, and (ii) cannot appear, for k=2, 3, 4 (assuming the values to
be distinct).
I am trying to study this for my midterm but its 3AM and I am stuck on this problem in the book as it does not provide a solution. Any help would be appreciated.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
如果您查看 Wikipedia 上的堆实现示例，您将看到第三大可以位于位置 2 或 3（无论第二大的不是哪一个），也可以位于位置 4+5 或 6+7（取决于第二大的位置）。因此，它可以是2-7。
然后，第四大的必须位于第三大可以位于的任何位置，加上第三大的直接子代的任何位置。这意味着它可以是 2 到 15 之间的任意值。
下图是从0开始的，因为是数组实现，所以位置加1。
If you look at the Heap Implementation example on Wikipedia, you will see that the third largest can be in position 2 or 3, whichever one the second largest is not, as well as positions 4+5 or 6+7, depending on where the second largest is. Thus, it can be in 2-7.
The fourth largest must then be in any position the third largest can be, plus any position which is a direct child of the third largest. This means it can be anywhere from 2-15.
The following picture is 0-based, as it is an array implementation, so add one for the position.