1
$\begingroup$

I'm having trouble making an algorithm to fit these specs:

  • Given a complete binary tree ($n = 2^d$ leaves) with integers in leaves.
  • Reading the leaves from left to right makes a sequence of integers (we can assume we have an array)

Goal: How can we minimize the number of inversions in that array only by choosing non-leaf nodes and swapping the the subtrees under the given nodes. For example, if the sequence is (4,2,1,3), then choosing the root (swapping its direct children) followed by choosing the right child of the root (and swapping its direct children) turns the sequence into (1,3,2,4), which has only one inversion. This would be the minimum number of inversions.

My approach: My idea was to use something like merge sort but modified. First i would recursively split the array and then when I merge back together I'd need to change the strategy. For the first level of merges (say I have the integers [2] and [1]) I can simply put those in the correct order because our swapping operation doesn't prevent this.

However, once I have to merge something like [1,2] and [3,4] (and larger groups which are powers of 2), I have to move those groups as single units (because of the operation we have to use). I can't put it in exact order like I want but I was thinking maybe it would be best to merge the larger groups by summing up all the numbers inside the groups and moving the groups with the smallest sums to the left to minimize inversions. That seems inefficient though. All the while I have to somehow count inversions. I'm really kind of lost on what to do besides what I've thought of so far. Would anyone be able to help?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
0
$\begingroup$

Let us denote by $L(x)$ the set of leaves in the subtree rooted at $x$. The idea is that the decision whether to switch the two children $x_1,x_2$ of $x$ depends only on $L(x_1),L(x_2)$, and depends on how many of the pairs $(a,b) \in L(x_1) \times L(x_2)$ satisfy $a < b$ and how many satisfy $b < a$.

If the sets $L(x_1),L(x_2)$ were available to you in their sorted forms, then you could count the number of pairs of each type by merging these sets and doing some accounting. This suggests a recursive algorithm which sorts the leaves using the merge sort strategy.

Details left to you.

Improve this answer
$\endgroup$
4
  • $\begingroup$ I've gotten as far as splitting recursively and then when I merge back up I would merge based on which subarray (left or right) has a smaller sum of its elements. The idea is that the one with the smaller sum would (hopefully?) be best to move to the left since it would result in less inversions. Then once everything is sorted I could run another procedure to count the inversions in the final array I just created. I'm not sure about the summing idea though (how I should know what subarray moves to the left side when merging). I'm also not sure if I can just count inversions while I'm doing it. $\endgroup$
    – user95596
    Commented Feb 10, 2019 at 17:15
  • $\begingroup$ You compute what you call sums during the merge procedure. You'll have to work it out. You don't have to count the inversions afterwards – this information should be available. $\endgroup$
    – Yuval Filmus
    Commented Feb 10, 2019 at 17:17
  • $\begingroup$ Just to be clear, 1. Are you saying it's possible to count the inversions of the resulting merged array while doing the merge routine? I don't see how you can know the total number of inversions that will be in the final array when you still have possible swaps to make while merging. 2. Are you also saying that the sums are a valid way of checking which subarray to move left? $\endgroup$
    – user95596
    Commented Feb 10, 2019 at 17:21
  • $\begingroup$ 1. Right, I'm saying that you can count inversions on the go. Given the inversions inside $L(x_1)$, the inversions inside $L(x_2)$, and the inversions across $L(x_1),L(x_2)$, the sum gives you the inversions inside $L(x)$. 2. You choose whether to switch or not according to the number of inversions across $L(x_1),L(x_2)$, which you can compute as part of your merge procedure. $\endgroup$
    – Yuval Filmus
    Commented Feb 10, 2019 at 17:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.