如何在1到n个不同元素的最大堆中找到第三小的元素可能的索引?我知道最小的元素会在叶子节点中。当n大于3时,第二小的元素将在n/2到n的任何位置。但我不知道如何计算第三小的元素。有什么建议吗?
[floor(n/4)+1,n]
。
i
的元素。它的直接子元素是2i
和2i+1
;它的孙子元素是4i, 4i+1, 4i+2, 4i+3
,通常情况下,它在级别k
的后代是2ki, 2ki+1, ..., 2ki + 2ki-1
, 简而言之,是[2ki, ..., 2k(i+1)-1 ]
。当然,这些范围是不重叠的(实际上,除非i
是1
,否则它们甚至不是连续的)。因此,如果i
至少有一个级别为k
的后代,则它也具有所有k' < k
的完整后代集合,其中有2k-2
个。
从所有这些中,我们可以得出结论:
如果 n ≥ 2ki 且 n < 2k(i+1)
,那么 i
具有:
2ki-2
个后代在某个水平小于 k
的级别上n - 2ki+1
个后代在水平 k
上;
总计: n-1
个后代。
如果 n ≥ 2k(i+1) 且 n < 2k+1i
,那么 i
具有:
2k+1-1
个后代。粗略地讲,这意味着堆的底层数组的前 1/2k
部分中找不到最后的 2k
个元素。