如何将二叉树转换为就地堆？

Question

我想到了以下几点：

< li >将树退化为链表，在退化的同时，用链表中的节点对象及其索引创建一个动态数组

看起来像这样

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

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]

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

Answer 1

>

我首先将树折叠成node.right上的有序链表。

我假设我们是从一个有序的BST开始的。如果不是，那就对列表进行排序。如果您希望使用最大堆而不是最小堆，那么此时也可以反转列表。

计算节点并计算解决方案中包含的最大完整树的深度

对整个树进行递归预排序遍历，随时从列表的头部填充每个节点。

对您刚刚构建的树进行预序遍历，从列表节点填充叶子，直到用完

步骤4将按如下方式递归完成：

root = list
fillChildren(root, list.right, levels-1)


fillChildren(root, list, levels) {
    if (levels < 1) {
        root.left = root.right = null
        return list
    }
    root.left = list
    list = fillChildren(root.left, list.right, levels-1)
    root.right = list
    list = fillChildren(root.right, list.right, levels-1)
    return list
}

当然，这样做的诀窍是，为了进行前序遍历而映射节点满足堆属性。

将第4步和第5步结合起来也很容易，只需跟踪一个虚拟数组堆中每个节点的索引。

只是为了好玩，整个工作是这样的:

treeToHeap(root) {

    if (root == null) {
        return null
    }

    // Convert tree to list

    while(root.left != null) {
        root = rotateRight(root)
    }
    for (n = root; n.right != null; n=n.right) {
        while (n.right.left != null) {
            n.right = rotateRight(n.right)
        }
    }

    // Count nodes
    count = 0
    for (n = root; n!=null; n=n.right) {
        count+=1
    }

    // Build min-heap
    
    list = root.right
    // root's index in imaginary array heap is 0
    
    if (count>1) {
        root.left = list
        list = fillNodes(root.left, list.right, 1, count)
    } else {
        root.left = null
    }
    if (count>2) {
        root.right = list
        list = fillNodes(root.right, list.right, 2, count)
    } else {
        root.right = null
    }
    return root
}

fillNodes(root, list, heapIndex, heapSize) {
    heapIndex = heapIndex*2+1
    if (heapIndex < heapSize) {
        root.left = list
        list = fillNodes(root.left, list.right, heapIndex, heapSize)
    } else {
        root.left = null
    }
    heapIndex += 1
    if (heapIndex < heapSize) {
        root.right = list
        list = fillNodes(root.right, list.right, heapIndex, heapSize)
    } else {
        root.right = null
    }
    return list
}

所以这花了15分钟（我没有费心写出rotateright），那是在弄清楚如何做到这一点之后。我返回了几次来修复错误。

对于一个30分钟的考试来说，这很难...但也许考试并没有真正要求堆完全平衡。如果只是实现一个就地heapify的问题，那么这是相当合理的。

Answer 2

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

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

戴-斯托特-沃伦算法的工作原理是将树旋转成一个单链表，然后从那里进行一系列旋转，将其变成一个完美平衡的树。我不记得DSW算法是否会根据二进制堆的需要，专门将所有剩余节点放在树的最左边的底层。如果没有，您可以通过进行清理来解决这个问题：如果树没有完全2次方的节点数，请从树的底层删除所有节点，然后通过顺序遍历遍历遍历树，将它们放在最左边。

至于heapify算法:通常的做法是从底部到顶部访问树的各个层。对于每个节点，您重复地将该节点与其较小的子节点交换，直到它小于所有子节点。有了显式树结构，这可以通过优雅的递归策略来实现:

< li >如果树没有子树，则停止。 < li >否则，递归地堆集左右子树，然后执行“向下冒泡”操作，反复用较小子树的值交换根树的值，直到它位于正确的位置。

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