3

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

例如，如果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

我想不出任何干净的算法可以做到这一点。任何解决方案/建议都会有帮助。

4

4 回答 4

2

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

  • 如果孩子的数量为 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}

然后的逻辑是找到 ak 使得 (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)
于 2012-09-21T13:46:43.833 回答
0

通过前序遍历，按排序顺序生成其元素的堆是由向量 (1,2,5,3,4,6,7) 表示的堆。不存在中序遍历按排序顺序生成键的堆。这是因为在堆中，父级总是小于其所有子级或大于其所有子级。由 (7,3,6,1,2,4,5) 表示的堆是在后序遍历期间按排序顺序生成其键的示例。

于 2015-04-05T16:57:19.123 回答
0

将前序遍历转换为标准堆表示应该很简单。预购访问自己，左，右。对于基于 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
于 2012-09-21T15:22:05.210 回答
0

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

你掌握的信息是：

  • 你有一棵二叉树
  • 所述树是堆排序的

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

二叉堆总是一棵完全二叉树。完全二叉树就是这样一棵二叉树，其中树的所有层都是满的，也许最后一层除外，它总是从左到右被填满。换句话说，堆不可能有一个内部节点少于两个子节点。

于 2012-09-21T13:26:58.600 回答