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 heapordered, 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 heapordering 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 3Notice 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 nonzero 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 6Notice 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 n1, 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 n1. If the node containing i is a left child, then element i1 of parent is the value of the node's parent. If the node containing i is a right child, then element i1 of parent is 100 plus the value of the parent. Note that parent is 0indexed. The node containing 0 is always the root, so its parent is not represented. For example, the skew heap 0 / \ 1 2 / / \ 5 4 3would be represented by parent = {0,100,102,2,1}, meaning that
No skew heap built entirely by inserts will ever contain a node with an empty left subtree and a nonempty right subtree. Such heaps will not be permitted as input.  
Definition  
 
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 nonnegative k, then the value k must also appear in parent.  
Examples  
0)  
 
1)  
 
2)  
 
3)  
 
4)  
