Блог пользователя qwi

Автор qwi, история, 3 года назад, По-английски

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

  • Проголосовать: нравится
  • +1
  • Проголосовать: не нравится

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Isn’t it simple descending sort?

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

    • »
      »
      »
      3 года назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      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.