最大堆中的第 k 个最大元素可能位于哪些级别？

Question

考虑一个包含

n

元素的最大堆。我有兴趣确定堆中第

k

最大元素可能所在的级别，即

2 <= k <= floor(n/2)

。假设所有元素都是不同的（这是来自 CLRS ed.4 的练习 6.1-5）。

鉴于索引

floor(n/2)+1

到

n

的节点是叶子，索引

1

处的节点是根，我们的重点是其他节点。已确定第

k

最大元素不能位于

k+1

层。这是因为第

k+1

层的节点有

k

个祖先，这意味着至少有

k

比它们大的元素。因此，它们不可能是第

k

最大元素。然而，确定可能发现第

k

最大元素的一般水平仍然是一个挑战。

我在这个平台上遇到了一个建议，建议在从

k

到

k

的索引内搜索最大堆中的第

2k

最大元素。虽然我理解下限背后的推理，但在数组排序的最佳情况下，第

k

最大元素位于索引

k

处，但我不确定为什么搜索应仅限于索引

2k

。这就提出了一个新问题：最大堆中索引

k

处的元素的高度是多少？

我将非常感谢任何有关此事的帮助！

Answer 1

坏消息。

• 如果k = 1，那么第一个元素当然是堆的根；
• 如果 k > 1，则第 k 个元素（1 索引）可以位于深度 2 和 min(k, h) 之间的任意位置，其中 h 是堆的高度。

考虑 n=31，k = 10，元素 1, ..., n，第 k 个最大元素为 22。（假设表达式“第 k 个最大元素”的索引为 1）

考虑以下两个 maxheap，它们具有相同的元素：

Heap a
31
[22] 30
21 20 29 28
19 18 17 16 27 26 25 24
 8  7  6  5  4  3  2  1 23 15 14 13 12 11 10  9

Heap b
31
30 27
29 26 25 24
28 23 21 20 19 18 17 16
[22] 15 14 13 12 11 10  9  8  7  6  5  4  3  2  1

这只是一个示例，但将其转化为证明相对容易，尽管用 n 、 n-1 和 n-2 而不是数值绘制这两个堆很乏味 :-p