Can't understand how to solve this problem.
Find a permutation of a given sequence A with N elements, such that it is a max-heap and when converting it to a sorted sequence, the total number of swaps in maxHeapify of line 25 in the pseudo code is maximal possible.
1 maxHeapify(A, i)
2 l = left(i)
3 r = right(i)
4 // select the node which has the maximum value
5 if l ≤ heapSize and A[l] > A[i]
6 largest = l
7 else
8 largest = i
9 if r ≤ heapSize and A[r] > A[largest]
10 largest = r
11
12 if largest ≠ i
13 swap A[i] and A[largest]
14 maxHeapify(A, largest)
15
16 heapSort(A):
17 // buildMaxHeap
18 for i = N/2 downto 1:
19 maxHeapify(A, i)
20 // sort
21 heapSize ← N
22 while heapSize ≥ 2:
23 swap(A[1], A[heapSize])
24 heapSize--
25 maxHeapify(A, 1)
Source: AOJ
Isn’t it simple descending sort?
Simple sorting is not working.
Test case input:
N = 8
A = 1 5 2 15 3 12 9 23
Test case output:
23 9 15 2 5 3 12 1
Note: there can be multiple correct solutions.
Oh, you want to maximize number of those swaps on line 13? That solution is pretty easy to see if you try their example on paper by hand (one of the best methods). See how they made smallest element to do all the work and all the swaps? Now it would be easy to grasp the principle.