Max heap with maximum number of total swaps

Правка en1, от qwi, 2021-08-10 20:19:35

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

Теги heap, aizu-oj

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский qwi 2021-08-10 20:19:35 1043 Initial revision (published)