Комбинаторные алгоритмы для программистов



             

Выбор - часть 2


Таким образом, пирамида, представленная на рисунке 15.3, принимает вид

 \begin{center} \begin{tabular}{ccccccccccccc} i: & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12\\ x_i & 94 & 93 & 75 & 91 & 85 & 44 & 51 & 18 & 48 & 58 & 10 & 34 \end{tabular} \end{center}

Заметим, что в пирамиде наибольшее имя должно находиться в корне и, таким образом, всегда в первой позиции массива, представляющего пирамиду. Обмен местами первого имени с

n
-м помещает наибольшее имя в его правильную позицию, но нарушает свойство пирамидальности в первых
n - 1
именах. Если мы можем сначала построить пирамиду, а затем эффективно восстановить ее, то все в порядке, так как тогда можно производить сортировку следующим образом: построить пирамиду из
x_1,x_2,\ldots,x_n
,


Это общее описание пирамидальной сортировки.

Использование турнира с выбыванием для отыскания наибольшего имени.Путь наибольшего имени показан жирной линией

Рис. 15.1.  Использование турнира с выбыванием для отыскания наибольшего имени.Путь наибольшего имени показан жирной линией


Рис. 15.2.  Отыскание второго наибольшего имени путем замены наибольшего имени на
- \infty
. Проведение повторного сравнения имен, побежденных наибольшим именем

Процедура RESTORE

(j,k)
восстановления пирамиды из последовательности
x_j,x_{j + 1},\ldots,x_k
в предположении, что все поддеревья суть пирамиды, такова:


Переписывая это итеративным способом и дополняя деталями, мы получим алгоритм 15.2.

Алгоритм 15.2.Восстановление пирамиды из дерева, поддеревья которого суть пирамиды

Алгоритм 15.2.Восстановление пирамиды из дерева, поддеревья которого суть пирамиды

Пирамида, содержащая 12 имен

Рис. 15.3.  Пирамида, содержащая 12 имен

Алгоритм 15.3.Пирамидальная сортировка

Алгоритм 15.3.Пирамидальная сортировка




Содержание  Назад  Вперед