查找最大堆中第k个元素的位置
Find the position of the k-largest element in max-heap
在这里做一些算法作业:(
我需要想出一个方程来找到最大堆数组中给定的第 k 个元素可能所在的所有可能位置。
i.e. the largest element (k=1) is at position n=1.
The second largest element (k=2) can be at positions n=2.
Element k=3 can also be in positions n=2.
...
The 6th largest element (k=6) can be in positions n=4 up to n=7.
etc.
没有真正想出可靠的计算方法。
如有任何意见，我们将不胜感激。
第 6 大元素可以远远。极端情况是前六个元素是根和一系列 right-children。每个 child 都位于节点 2n+1，其中 n 是 parent 的节点。 right-most 序列的索引序列是 1, 3, 7, 15, 31, 63 (a.k.a. 2^6-1)。其他较小的值填充在每个分支的左侧。
最早的位置是如果相同的值恰好是根的 left-child，而所有其他值都去了正确的分支：它出现在位置 2。同样，根据需要出现较小的值.
因此，可能值的 范围 是从 2 到 2^n-1。
您剩下的问题是确定剩余位置中的哪些位置可以包含第 6 大元素。
画一棵适当深度的树——更好的是，只画 4 层深，并使用第 4 大元素。比如说，使用 99、98、98、96，然后 "other" 值可以是 1 到 11。在这棵树上有什么地方可以放 96 而 不能 将其他数字排列成合法树？
再将树展开一层。 现在哪里有不能放的洞96?
这让你 un-stuck 了吗？
n 项堆的高度（称为 h）为 log2(n)，四舍五入。假设一个完整的最小堆，第 k 个项目几乎可以在任何地方，但要遵守以下限制。
- 第一项 (k == 1) 必须在根部。
- 最大的项目 (k == n) 必须在叶级。
- 第k个节点的级别不能大于k。
- 第k个节点的层数不能小于(h-log2(n-k)+1).
考虑一个有 7 个级别的完整堆。堆本身有 127 个节点。第 2 层的每个节点都是 63 个节点的完整堆。因此，第二层的每个项目都必须在其下方有 62 个更小的值。第 96 个最小的项目不可能在第二层，因为没有 62 个更大的值来填充它的树。
这些规则可以帮助您将顺序搜索括起来，但对您并没有多大用处。 7层堆中第96个最小的项目可以向上到第3层，向下到第7层。节点不可能在的位置只有三个。
如果您使用的是最大堆，请将上面的 "smallest" 更改为 "largest."
在这里做一些算法作业:(
我需要想出一个方程来找到最大堆数组中给定的第 k 个元素可能所在的所有可能位置。
i.e. the largest element (k=1) is at position n=1.
The second largest element (k=2) can be at positions n=2.
Element k=3 can also be in positions n=2.
...
The 6th largest element (k=6) can be in positions n=4 up to n=7.
etc.
没有真正想出可靠的计算方法。
如有任何意见，我们将不胜感激。
第 6 大元素可以远远。极端情况是前六个元素是根和一系列 right-children。每个 child 都位于节点 2n+1，其中 n 是 parent 的节点。 right-most 序列的索引序列是 1, 3, 7, 15, 31, 63 (a.k.a. 2^6-1)。其他较小的值填充在每个分支的左侧。
最早的位置是如果相同的值恰好是根的 left-child，而所有其他值都去了正确的分支：它出现在位置 2。同样，根据需要出现较小的值.
因此，可能值的 范围 是从 2 到 2^n-1。 您剩下的问题是确定剩余位置中的哪些位置可以包含第 6 大元素。
画一棵适当深度的树——更好的是，只画 4 层深，并使用第 4 大元素。比如说，使用 99、98、98、96，然后 "other" 值可以是 1 到 11。在这棵树上有什么地方可以放 96 而 不能 将其他数字排列成合法树？
再将树展开一层。 现在哪里有不能放的洞96?
这让你 un-stuck 了吗？
n 项堆的高度（称为 h）为 log2(n)，四舍五入。假设一个完整的最小堆，第 k 个项目几乎可以在任何地方，但要遵守以下限制。
- 第一项 (k == 1) 必须在根部。
- 最大的项目 (k == n) 必须在叶级。
- 第k个节点的级别不能大于k。
- 第k个节点的层数不能小于(h-log2(n-k)+1).
考虑一个有 7 个级别的完整堆。堆本身有 127 个节点。第 2 层的每个节点都是 63 个节点的完整堆。因此，第二层的每个项目都必须在其下方有 62 个更小的值。第 96 个最小的项目不可能在第二层，因为没有 62 个更大的值来填充它的树。
这些规则可以帮助您将顺序搜索括起来，但对您并没有多大用处。 7层堆中第96个最小的项目可以向上到第3层，向下到第7层。节点不可能在的位置只有三个。
如果您使用的是最大堆，请将上面的 "smallest" 更改为 "largest."