CLRS习题6.1-5：最大堆中第k大元素的层级与索引范围疑问

一、为什么第k大元素的查找上限是2k #

最大堆的核心性质是：所有父节点的值严格大于其子节点的值（元素全不同），且索引为i的节点，其父节点为floor(i/2)，子节点为2i和2i+1。

针对索引i > 2k的节点，推导如下：

• 该节点的父节点是floor(i/2)，由于i > 2k，则floor(i/2) ≥ k（例如i=2k+1时，floor(i/2)=k；i>2k+1时，floor(i/2)≥k+1）。
• 父节点floor(i/2)的祖先链包含索引1,2,...,k-1（共k-1个节点），这些节点的值均大于父节点的值，而父节点的值又大于节点i的值。
• 算上父节点本身，至少有k个元素（索引1到k对应的元素）比节点i的值大，这意味着节点i对应的元素最多是第k+1大，不可能是第k大。

因此，第k大元素的索引不可能超过2k，查找上限为2k。

二、索引k处元素在最大堆中的高度 #

堆中节点的高度定义为从该节点到任意叶节点的最长路径上的边数（叶节点高度为0），有两种直观计算方式：

1. 基于索引的推导：
   找到最大的整数h，满足k * 2^h ≤ n，这个h就是节点k的高度。因为每向下一层，节点索引会乘以2，直到无法再向下（即超过n），此时的层数差就是高度。
   示例：当n=7、k=2时，2*2^1=4≤7，2*2^2=8>7，则h=1，符合实际（节点2的子节点是叶节点，路径边数为1）。

2. 基于层数的推导：

   • 根节点（索引1）为第1层，节点k所在的层数是floor(log₂k) + 1。
   • 叶节点所在的层数是floor(log₂n) + 1。
   • 节点k的高度 = 叶节点层数 - 节点k的层数。
     示例：当n=8、k=2时，叶节点层数是4，节点2的层数是2，高度为4-2=2，符合实际（节点2→4→8，路径边数为2）。

两种方法计算结果一致，可根据习惯选择。

内容的提问来源于stack exchange，提问作者user22785544