Given an array A[] which represents a Complete Binary Tree i.e, if index i is the parent, index 2i + 1 is the left child and index 2i + 2 is the right child.
The task is to find the minimum number of swaps required to convert it into a Binary Search Tree.
Example 1:
Input:
A[] = { 5, 6, 7, 8, 9, 10, 11 }
Output: 3
Explanation:
Binary tree of the given array:
Swap 1: Swap node 8 with node 5.
Swap 2: Swap node 9 with node 10.
Swap 3: Swap node 10 with node 7.
So, minimum 3 swaps are required.
Example 2:
Input:
A[] = {1, 2, 3}
Output: 1

Your Task:
You don't need to read input or print anything. Your task is to complete the function minSwaps() which takes an array A[] and returns an integer as output.
Expected Time Complexity: O(NlogN)
Expected Auxiliary Space: O(N)

Constraints:
1 <= N <= 10^{5}

见题面

见题面