在这里做一些算法作业:(
我需要想出一个方程来找到最大堆数组中给定的第 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\3.
Element k=3 can also be in positions n=2\3.
...
The 6th largest element (k=6) can be in positions n=4 up to n=7.
etc.
没有真正想出可靠的计算。
如有任何意见，我们将不胜感激。
最佳答案
第 6 大元素可以远远。极端情况是前六个元素是根和一系列右 child 。每个 child 都在节点 2n+1 处，其中 n 是父节点。最右边序列的索引序列是 1、3、7、15、31、63(又名 2^6-1)。其他较小的值填充在每个分支的左侧。
最早的位置是如果相同的值恰好是根的左子节点，而所有其他值都转到右分支:它出现在位置 2 中。同样，根据需要出现较小的值。
所以，可能值的范围是从 2 到 2^n-1。 您剩下的问题是确定剩余位置中的哪些位置可以包含该第 6 大元素。
画一棵适当深度的树——更好的是，只画 4 层深，并使用第 4 大元素。比如，使用 99、98、98、96，然后“其他”值可以是 1 到 11。在这棵树上有什么地方可以放置 96 而您不能 将其他数字排列成一棵合法的树？
再将树展开一层。 现在不能放置 96 的孔在哪里？
这会让你摆脱困境吗？
关于algorithm - 查找最大堆中第k个元素的位置，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/49638177/