### Problem Statement

Skew heaps are an excellent implementation of priority queues. A skew heap is a binary tree like a binary search tree, but with a different ordering of its elements. In a skew heap, the elements are heap-ordered, meaning that every child is larger than its parent. A left sibling is not required to be smaller than its right sibling, and skew heaps are not required to be balanced. The heap-ordering property implies that the minimum element in a skew heap is always the root.

Inserting a new element X into a skew heap H is done recursively. The base case applies when H is empty or when X is smaller than the existing root. The new element becomes the new root, with the old root as its left child. The recursive case applies when X is larger than the existing root. The left and right subtrees of the existing root are swapped, and X is inserted recursively into the left subtree (which was the right subtree before the swap). These two cases are illustrated below.

```
BASE CASE (H is empty or X < root of H)
---------------------------------------
Insert(X, H) ===>   X
/
H

RECURSIVE CASE (X > Y)
---------------------------------------
Insert(X,  Y  ) ===>            Y
/ \                  / \
A   B       Insert(X,B)  A
```

The following snapshots show the results of sequentially inserting the numbers 0,1,2,3,4,5,6 into an initially empty tree (where all children not shown are assumed to be null):

```
0    0    0        0        0         0           0
/    / \      / \      / \       / \         / \
1    2   1    1   2    2   1     /   \       /   \
/        /   /     1     2     2     1
3        4   3     / \   /     / \   / \
5   3 4     6   4 5   3
```
Notice how, because of the swaps, new elements are distributed evenly between the two sides of the tree. In this case, the odd elements (1,3,5) are placed on one side of the tree, and the non-zero even elements (2,4,6) are placed on the other side of the tree.

On the other hand, it is also possible to get an unbalanced tree if the elements are not inserted in sorted order. For example, sequentially inserting the numbers 6,4,5,2,0,1,3 into an initially empty tree yields

```
6    4    4        2        0     0         0
/    / \      /        /     / \       / \
6    5   6    4        2     1   2     2   1
/ \      /         /     / \
5   6    4         4     3   4
/ \       / \       / \
5   6     5   6     5   6
```
Notice how elements inserted after the overall minimum element are distributed evenly between the left and right subtrees of the root (e.g., 1 and 3 in the last tree above). In contrast, elements inserted before the overall minimum element end up in the same subtree of the root (e.g., 6, 4, 5, and 2 above).

Your task is to write a method that will take a skew heap and return the sequence of insertions that might have created that heap. If more than one sequence of insertions might have created the final skew heap, return the lexicographically earliest. A sequence A is lexicographically earlier than a sequence B if the element of A at the leftmost position at which the sequences differ is smaller than the element of B at the same position.

The input heap contains the values 0 through n-1, inclusive, where n is the size of the heap. Each value appears exactly once in the heap. The shape of the input tree will be represented by a int[], parent, of size n-1. If the node containing i is a left child, then element i-1 of parent is the value of the node's parent. If the node containing i is a right child, then element i-1 of parent is 100 plus the value of the parent. Note that parent is 0-indexed. The node containing 0 is always the root, so its parent is not represented. For example, the skew heap

```              0
/ \
1   2
/   / \
5   4   3
```
would be represented by parent = {0,100,102,2,1}, meaning that
• 1 is the left child of 0.
• 2 is the right child of 0.
• 3 is the right child of 2.
• 4 is the left child of 2.
• 5 is the left child of 1.

No skew heap built entirely by inserts will ever contain a node with an empty left subtree and a non-empty right subtree. Such heaps will not be permitted as input.

### Definition

 Class: SkewHeaps Method: history Parameters: int[] Returns: int[] Method signature: int[] history(int[] parent) (be sure your method is public)

### Constraints

-parent contains between 1 and 50 elements, inclusive.
-Element i of parent is either between 0 and i, inclusive, or between 100 and 100+i, inclusive.
-No value appears more than once in parent.
-If the value 100+k appears in parent, for some non-negative k, then the value k must also appear in parent.

### Examples

0)

 `{ 100, 0, 101, 102, 1, 2 }`
`Returns: { 0,  1,  2,  3,  4,  5,  6 }`
 The tree ``` 0 / \ / \ 2 1 / \ / \ 6 4 5 3 ```
1)

 `{ 100, 0, 2, 102, 4, 104 }`
`Returns: { 4,  6,  5,  2,  0,  1,  3 }`
 The tree ``` 0 / \ 2 1 / \ 3 4 / \ 5 6 ``` Either {4,6,5,2,0,1,3} or {6,4,5,2,0,1,3} could have created this tree, so we return the lexicographically smallest.
2)

 `{ 0, 100, 1, 102, 2, 3, 5 }`
`Returns: { 2,  5,  0,  3,  4,  6,  7,  1 }`
 The tree ``` 0 / \ 1 2 / / \ 3 5 4 / / 6 7 ``` There are eight sequences that could have produced this tree: ``` {2,5,0,3,4,6,7,1} {2,5,0,6,4,3,7,1} {2,7,0,3,4,6,5,1} {2,7,0,6,4,3,5,1} {5,2,0,3,4,6,7,1} {5,2,0,6,4,3,7,1} {7,2,0,3,4,6,5,1} {7,2,0,6,4,3,5,1} ``` We choose the lexicographically smallest.
3)

 `{ 0 }`
`Returns: { 0,  1 }`
 The tree ``` 0 / 1 ```
4)

 `{ 100, 1, 101, 103, 3, 4, 6, 107, 7, 0, 10, 11, 110, 12, 112, 111, 8, 108, 2, 16 }`
```Returns:
{ 8,  18,  17,  7,  9,  0,  11,  6,  12,  4,  16,  3,  15,  1,  20,  2,  10,  5,  13,  19,  14 }```

#### Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=1318

#### Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=4707&pm=1318

vorthys

#### Testers:

lbackstrom , brett1479

Search