时间戳

首页 > 解决方案 > 如何将二叉树原地转换成堆？

algorithm - 如何将二叉树原地转换成堆？

问题描述

我想到了以下几点：

  1. 将树退化为链表，在退化的同时，将节点对象及其在链表中的索引组成一个动态数组

它看起来像这样

def treeDegenerator(self):
    self.valList = []
    currentNode = self
    self.totalNodes = 0 
    self.nodes = 0
    while currentNode:
        while currentNode.getLeftChild():
            currentNode.rotate_root_right()
        self.valList.append(currentNode)
        currentNode = currentNode.getRightChild()
        self.totalNodes += 1
  1. 使用动态数组，取消引用所有左孩子和右孩子，并使用（索引值）* 2 + 1将退化树转换为完整的树，得到左孩子，右边再加1。
def completeTree():
    for node in self.valList:
        node.left = None
        node.right = None
        
    for i in range(len(self.valList)):
        self.valList[i].left = self.valList[(i)*2+1]
        self.valList[i].right = a.valList[(i)*2+2]
  1. 通过从底部开始逐级比较每个节点的子节点，通过移位值变成堆。

这是一个学生必须在没有任何过去考试参考的情况下编写代码的问题。我的方法的问题是，我几乎不可能在 30 分钟内正确地写下所有代码，如果我事先记住一些代码，也许有可能。我想知道是否有更简单、更可行和优雅的解决方案将任何二叉树变成一个堆？

标签： algorithmdata-structurestreebinary-treeheap

解决方案

从概念上讲，您可以将此任务分解为两个步骤：

  1. 将树重建为完美平衡的 BST，底部行从左到右填充。您可以使用Day-Stout-Warren 算法的修改版本来做到这一点。
  2. 运行heapify 算法将你的树转换成二叉堆。这可以非常漂亮地递归完成；详情见下文。

Day-Stout-Warren 算法的工作原理是将树旋转成单链表，然后从那里应用一系列旋转将其变成完美平衡的树。我不记得 DSW 算法是否专门将所有剩余节点放置在最左边的树的底层，根据二进制堆的需要。如果没有，您可以通过清理过程来解决此问题：如果树没有完美的 2 次幂的节点数，则从树的底层删除所有节点，然后使用为了遍历将它们放在最左边。

至于 heapify 算法：这通常是通过从底部到顶部访问树的层来完成的。对于每个节点，您反复将该节点与其较小的子节点交换，直到它小于其所有子节点。使用显式树结构，这可以通过优雅的递归策略来完成：

  • 如果树没有孩子，就停下来。
  • 否则，递归地堆积左子树和右子树，然后执行“冒泡”传递，反复将根的值与其较小的孩子的值交换，直到它在正确的位置。

这总体上需要 O(n) 时间并且仅使用 O(log n) 辅助存储空间，这是堆栈帧实现这两种算法所需的空间。

<editorializing> 话虽如此 - 这似乎是一个非常糟糕的编码问题，无法进行 30 分钟的定时考试。您可以很好地掌握算法以及如何对其进行编码，但却不记得这里两个子步骤中涉及的所有步骤。在半小时内提出这个问题，本质上是在测试“你是否已经非常详细地记住了各种不相关算法的实现？”，这似乎不是一个好的目标。</编辑>

推荐阅读