查找最大堆中k个最大元素的位置

第六大元素可以是 很 更远的地方。极端的情况是,前六个元素是根元素和一系列正确的子元素。每个子节点都位于节点 2n+1 哪里 n 是父节点。最右侧序列的索引顺序为1、3、7、15、31、63(也称为2^6-1)。另外,较小的值填充在每个分支的左侧。

最早的位置是,如果相同的值恰好是根的左子级,而其他所有值都是右分支:它出现在位置2。同样,根据需要显示较小的值。

所以 范围 可能值的范围为2到2^n-1。 剩下的问题是确定剩下的哪个位置可以包含第六大元素。

画一棵适当深度的树——更好的是,只画4层深的树,并使用第四大元素。例如,使用99、98、98、96,然后“其他”值可以是1到11。这棵树上有什么地方可以放 96 就是你 不能 将其他数字排列成一棵法律树?

将树再展开一级。 现在 你不能放进去的洞在哪里 96 ?

这能让你摆脱困境吗?

n个项目的堆的高度(称为h)为log _2. (n) ,向上取整。假设有一个完整的最小堆,第k个项目几乎可以在任何地方,但要受到以下限制。

1. 第一项(k==1)必须位于根。
2. 最大项目(k==n)必须位于叶级别。
3. 第k个节点的级别不能大于k。
4. 第k个节点的级别不能小于(h-log _2. (n-k)+1)。

考虑7个级别的完整堆。堆本身有127个节点。第二级的每个节点都是63个节点的完整堆。因此,第二级的每个项目都必须有62个较小的值。第96个最小的项目不可能位于第二级,因为没有62个更大的值来填充其树。

这些规则可以帮助您支持顺序搜索,但它并没有给您带来很多好处。在7级堆中,第96个最小的项可以高达3级,也可以低至7级。节点只能处于三个位置。

如果您使用的是最大堆,请将上面的“最小”更改为“最大”