如何将二叉树原地转化为堆？

Question

我想到了以下几点：

将树退化为链表，并在退化的同时，使具有节点 object 及其在链接中的索引的动态数组名单

看起来像这样

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

使用动态数组，解引用所有左 child 和右 child 并将退化树转换为完整树使用 (index value)*2+1 得到左边 child，右边加 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]

通过比较每个节点的children，从底部开始，逐层移动值变成堆。

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

Answer 1

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

将树重建为 perfectly-balanced BST，底行由 left-to-right 填充。您可以使用 Day-Stout-Warren algorithm.
运行 heapify algorithm 将您的树转换为二叉堆。这可以递归地非常漂亮地完成；详情见下文。

Day-Stout-Warren 算法的工作原理是将树旋转成 singly-linked 列表，然后从那里应用一系列旋转将其变成 perfectly-balanced 树。我不记得 DSW 算法是否会根据二叉堆的需要专门将所有剩余节点放在最左边的树的底层。如果不是，您可以通过执行清理过程来解决此问题：如果树没有一定数量的节点是 2 的完美幂，则从树的底层移除所有节点，然后使用顺序遍历把它们放在最左边。

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

如果树没有children，停止。
否则，递归堆化左子树和右子树，然后执行“bubble-down”遍，重复交换根的值与其较小的 child 的值，直到它在正确的位置。

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

话虽这么说 - 这似乎是一个非常糟糕的编码问题，不能放在 30 分钟的计时考试中。您可能精通算法以及如何对它们进行编码，但不记得此处两个子步骤中涉及的所有步骤。半个小时问这个，本质上是在测试“你有没有很详细地记住各种不相关算法的实现？”，这似乎不是一个好的目标。

Answer 2

我会先将树折叠成 node.right 上的有序链表。
我假设我们从有序的 BST 开始。如果不是，则对列表进行排序。如果你想要一个最大堆而不是最小堆，那么此时也反转列表。
对节点进行计数，计算解中包含的最大完整树的深度
对整个树进行递归前序遍历，边走边从列表的头部填充每个节点。
对您刚刚构建的树进行预序遍历，从列表节点填充叶子，直到运行 out

第 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 分钟的考试来说，这是相当困难的......但也许考试并不真正要求堆达到完美平衡。如果只是实现一个in-place heapify的问题，那还是比较合理的。

如何将二叉树原地转化为堆？

How to transform a binary tree into a heap in place?

algorithm

heap

tree

binary-tree

data-structures