堆中最大的物品 [英] Largest Item in Heap

问题描述

堆中最大的项目必须出现在位置1，第二大的项目必须出现在位置1. 处于位置2或位置3.给出大小为31的堆中的位置列表，其中 第k个最大的(i)可以出现，而(ii)不能出现，因为k = 2、3、4(假设值为 截然不同).

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).

我正在为期中课程进行研究，但该课程在凌晨3点进行，由于无法提供解决方案，因此我将其卡在书中.任何帮助将不胜感激.

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.

推荐答案

如果您查看 Wikipedia上的堆实现" 示例中，您会看到第三大的位置可能在第2或3位，第二大的位置不在其中，还有4 + 5或6 + 7的位置，具体取决于第二个位置最大的是.因此，它可以在2-7.

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.

那么第四位必须位于第三位的任何位置，再加上第三位的直接子级的任何位置.这意味着它可以在2到15之间的任何地方.

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.

下面的图片是基于0的，因为它是一个数组实现，因此请为该位置添加一个.

The following picture is 0-based, as it is an array implementation, so add one for the position.

这篇关于堆中最大的物品的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！