自下而上的堆构造不完全依赖于(n+1)是2的幂吗?(其中n是节点数)。
例如,考虑n=21的情况。(n+1)不是2的幂-这怎么工作?
您可以创建第一个insert(n+1)/2节点,也就是说11个节点然后插入(n+1)/4个节点作为先前插入节点的父节点,或者换句话说,插入5.5个节点。但如何才能插入“半个节点”当n不是2的幂时,在某种程度上总是会得到十进制数量的节点插入-如何处理这个问题?
我考虑移除一定数量的节点,使剩余的节点是2的幂,从剩余的节点构建一个树,然后在完成后将移除的节点冒泡到树中。但是,对于大量的节点,这变得不可行:即节点数=1600。最接近的2的幂是1024,这意味着您将不得不冒泡576个节点,这是相对耗时的。
最佳答案
不,这是没有要求的记住,二进制堆的最后一层可能缺少节点这意味着,在第一步中,将节点组合在一起,最终形成堆的集合,这样这些堆将形成堆的最后两层。不是所有这些堆都必须是完整的堆;其中一些会有失踪的孩子。
如果选择要忽略的子节点数,使剩余的节点数小于完全幂的1,则可以像往常一样进行自下而上的构造结果将是一个完整的二进制堆。
希望这有帮助!
关于algorithm - 自下而上的堆构造是否完全取决于(n + 1)是2的幂的事实?,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/11354444/