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

Question

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

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

堆的大小为7

1 是堆中的第一个元素（考虑到堆表示为数组）

下一个（大小-1）/2元素将位于1的左子树中

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

最后一个（大小 - 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

将前序遍历转换为标准堆表示应该很简单。预订单访问自己，左，右。对于基于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

Answer 2

你试图通过应用给你的两条信息中的一条来解决这个问题。

你掌握的信息是:

• 你有一个二叉树
• 对所述树进行堆排序

现在，虽然您通常需要两次二进制遍历才能获得第三次遍历（前、后，依次为三次），但这里有一个额外的信息：二进制树是一个堆。

二叉堆总是一棵完整的二叉树。完整的二叉树是这样一棵二叉树，树的所有级别都满了，也许除了最后一个级别，它总是从左到右填充。换句话说，堆不可能有一个小于两个子节点的内部节点。

Answer 3

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

< li >如果子代数量为2，则拆分为:(1，1) < li >如果子代数为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）

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)