qwi's blog

Max heap with maximum number of total swaps
By qwi, history, 3 years ago, In English

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

  • Vote: I like it
  • +1
  • Vote: I do not like it

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Isn’t it simple descending sort?

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      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.

      → Reply