给定堆的前序遍历，构造堆

Question

我在互联网上看到了这个问题，并试图解决它。我可以解决堆是严格二叉树的情况(通过重复划分前序遍历)，但当堆只是一棵完整的二叉树时，我无法找出算法。

例如，如果1, 2, 3, 4, 5, 6, 7是最小堆的预序遍历，

堆的大小为7

1是堆中的第一个元素(考虑一下，堆表示为一个数组)

下一个(size - 1) / 2元素将位于1的左子树中

2, 3, 4将位于1的左子树中

最后一个(size - 1) / 2元素将位于1的右子树中

5, 6, 7将位于1的右子树中

可以通过递归地应用此逻辑来构造完整的堆。

该解决方案适用于这样的情况，即堆是严格二叉树

       1
    2     3
  4   5  6  7

但显然，这在堆的情况下不起作用，在堆中，非叶元素有一个子元素或没有子元素。例如，

          1                1
       2     3         2     3
     4   5  6        4     5

我想不出任何干净的算法可以做同样的事情。任何解决方案/建议都会很有帮助。

Answer 1

看几个例子会让这变得更容易。随着孩子数量的增加，我们看到了以下模式：

如果子代的数量为2，则拆分为：(1，1)

• 如果子代的数量为3，则拆分为：(2，1)

继续这样，当孩子的数量在2到6之间时，我们得到以下拆分：

(1, 1), (2, 1), (3, 1), (3, 2), (3, 3)

当孩子的数量在6到14之间时，我们得到：

(3, 3), (4, 3), (5, 3), (6, 3), (7, 3), (7,4), (7, 5), (7, 6), (7, 7)

因此，当子对象的数量介于(2^k-2)和(2^{k+1}-2)之间时，我们得到：

 either a split of the form (2^{k-1}-1+l, 2^{k-1}-1) where   0 <= l <= 2^{k-1} or
                            (2^k-1, 2^{k-1}-1+l)     where   0 <= l <= 2^{k-1}

然后，逻辑是找到一个k，使得(2^k-2) <= childCount <= (2^{k+1}-2)并按如下方式拆分：

Let l = childCount - (2^k-2)
If  l <= 2^{k-1} 
    split with (2^{k-1}-1+l, remaining)
Else 
    split with (2^k-1, remaining)

Answer 2

您试图通过仅应用提供给您的两条信息中的一条来解决此问题。

您拥有的信息是：

你有一个二叉树，，

• ，

，

• ，

，，这棵树是堆排序的

现在，虽然您通常需要两次二叉遍历才能获得第三次遍历(前、后、按顺序是三次)，但在这里，您有了额外的信息:二叉树是一个。

二进制堆始终是一个完整的二叉树。完整的二叉树是这样的二叉树，其中树的所有级别都是满的，可能除了最后一层，它总是从左到右填充。换句话说，堆不可能有一个少于两个子节点的内部节点。

Answer 3

将预排序遍历转换为标准的堆表示应该很简单。预购访问self，左，右。对于从1开始的数组中的堆，节点N的左子节点是2N，右子节点是2N+1。这直接导致了这个算法：

def constructHeap(preorder, pidx, heap, hidx)  
    return pidx if (hidx>=heap.size)         #no more children
    heap[hidx] = preorder[pidx]              #self
    pidx = constructHeap(preorder, pidx+1, heap, hidx*2) #left
    return constructHeap(preorder, pidx, heap, hidx*2+1) #right
end

preorder = [1,2,3,4,5,6,7]
heap = Array.new(preorder.size+1)            #create storage
constructHeap(preorder, 0, heap, 1)
puts heap