Given the preorder traversal of a heap, construct the heap

3
votes

Saw this question somewhere in the internet and tried to solve it. I could solve it for cases where the heap is a strictly binary tree (by repeatedly partitioning the preorder traversal) but could not figure out an algorithm when the heap is only a complete binary tree.

For eg, if 1, 2, 3, 4, 5, 6, 7 is the preorder traversal of a min-heap,

size of the heap is 7

1 is the first element in the heap (considering, the heap is represented as an array)

The next (size - 1) / 2 elements will be in the left sub-tree of 1

2, 3, 4 will be in the left sub-tree of 1

The last (size - 1) / 2 elements will be in the right-sub tree of 1

5, 6, 7 will be in the right sub-tree of 1

The complete heap can be constructed by applying this logic recursively.

The solution will work for cases like these where the heap is a strictly-binary tree

       1
    2     3
  4   5  6  7

But apparently, this does not work in case of heap where a non-leaf element has one or no children. For eg,

          1                1
       2     3         2     3
     4   5  6        4     5

I couldn't think of any clean algorithms that could do the same. Any solutions/suggestions will really help.

4
algorithmheaptree-traversal
A binary heap is a complete tree by definition, so the situation you are describing where it won't work - cannot happen in a binary heap. Are you talking about a binary heap? – amit
considering, the heap is represented as an array, no, it is represented as pre-order traversal. Forget how it's stored in an array. – phant0m
But apparently, this does not work in case of heap where a non-leaf element has one or no children. I couldn't think of any clean algorithms that could do the same. can you please give such an example so we're all talking about the same thing? – phant0m
@phant0m, imagine a tree of size four: A's children are B and C, B's child is D. This is a complete binary tree where a non-leaf element has one child. I don't think the other situation (no children) is possible, as a non-leaf node must by definition have at least one child. – Kevin
@Kevin, No, I meant an example pre-order traversal that shows where his idea fails. He only provided an in-depth example where his idea works, as far as I understood, but not one where it fails, which would be more interesting. Further, everyone can then present a solution based on the same example. – phant0m

4 Answers

2
votes

Looking at a few examples will make this easier. We see the following pattern as the number of children increase:

  • If number of children is 2 the split is: (1, 1)
  • If number of children is 3 the split is: (2, 1)

Continuing this way when the number of children is between 2 and 6 we get the following splits:

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

When the number of children is between 6 and 14 we get:

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

So when the number of children is between (2^k-2) and (2^{k+1}-2) we get:

 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}

The logic then would be to find a k such that (2^k-2) <= childCount <= (2^{k+1}-2) and split as follows:

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)
0
votes

You are trying to solve this by only applying one of two pieces of information given to you.

The information you have is:

  • you have a binary tree
  • the said tree is heap-sorted

Now, while it is true you commonly need two binary traversals to get the third one (pre-, post-, in-order being the three), here, you have an extra information: The binary tree is a heap.

A binary heap is always a complete binary tree. A complete binary tree is such a binary tree where all the levels of the tree are full, except perhaps the last level, which is always filled from left to right. In other words, it is impossible for the heap to have an inner node with less then two children.

0
votes

Converting the pre-order traversal to the standard heap representation should be straightforward. The pre order visits self, left, right. For a heap in a 1-based array, the left child of node N is at 2N and the right child is 2N+1. That leads directly to this algorithm:

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
0
votes

With a preorder traversal, a heap that produces its elements in sorted order is that which is represented by the vector (1,2,5,3,4,6,7). There does not exist a heap for which an inorder traversal produces the keys in sorted order. This is because in a heap the parent is always less than all of its children or greater than all of its children. The heap represented by (7,3,6,1,2,4,5) is an example of one which produces its keys in sorted order during a postorder traversal.