Презентация «Пирамидальная сортировка HeapSort. Пирамида Хеопса»

Смотреть слайды в полном размере
Презентация «Пирамидальная сортировка HeapSort. Пирамида Хеопса»

Вы можете ознакомиться с презентацией онлайн, просмотреть текст и слайды к ней, а также, в случае, если она вам подходит - скачать файл для редактирования или печати. Документ содержит 15 слайдов и доступен в формате ppt. Размер файла: 2.72 MB

Просмотреть и скачать

Pic.1
Пирамидальная сортировка HeapSort Пирамида Хеопса
Пирамидальная сортировка HeapSort Пирамида Хеопса
Pic.2
Пирамидальная сортировка или метод Вильямса – Флойда ( Williams, Floyd, 1964) Пирамидальная сортиров
Пирамидальная сортировка или метод Вильямса – Флойда ( Williams, Floyd, 1964) Пирамидальная сортировка основана на алгоритме построения пирамиды. Определение Последовательность aL , aL+1 , … , aR …
Pic.3
Пример 2 3 4 5 6 7 8 - пирамида 3 2 6 3 4 5 7 1 2 3 4 5 6 7 - не пирамида
Пример 2 3 4 5 6 7 8 - пирамида 3 2 6 3 4 5 7 1 2 3 4 5 6 7 - не пирамида
Pic.4
Построение пирамиды Пусть aL+1 , …, aR - пирамида, необходимо добавить элемент Х, чтобы получить нов
Построение пирамиды Пусть aL+1 , …, aR - пирамида, необходимо добавить элемент Х, чтобы получить новую пирамиду aL , …, aR. Новый элемент добавляем в начало, расширяя последовательность влево. Если …
Pic.5
Построение пирамиды Иначе найдутся такие a2L или a2L+1 , что не будут удовлетворять условию пирамиды
Построение пирамиды Иначе найдутся такие a2L или a2L+1 , что не будут удовлетворять условию пирамиды. Возьмем минимальный элемент из a2L и a2L+1 , обозначим его за aj и обменяем с aL . В результате …
Pic.6
Построение пирамиды Теперь элемент Х попал на место aj и для него необходимо проверить условие пирам
Построение пирамиды Теперь элемент Х попал на место aj и для него необходимо проверить условие пирамиды, и так до конца массива. Пример: 1 2 3 4 5 6 7 8 3 2 6 3 4 5 7 6 3 2 6 3 4 5 7 2 3 6 6 3 4 5 7 …
Pic.7
Построение пирамиды (L ,R) Алгоритм на псевдокоде aL+1, …, a R – на входе пирамида (L+1,R) aL – новы
Построение пирамиды (L ,R) Алгоритм на псевдокоде aL+1, …, a R – на входе пирамида (L+1,R) aL – новый элемент x := aL, i := L DO j := 2i IF ( j>R) OD FI IF ( j<R и aj+1  aj ) j=j+1 FI IF ( …
Pic.8
Трудоемкость алгоритма Трудоемкость алгоритма построения пирамиды Определим верхнюю границу трудоемк
Трудоемкость алгоритма Трудоемкость алгоритма построения пирамиды Определим верхнюю границу трудоемкости алгоритма. На каждой итерации цикла выполняется максимум два сравнения и одна пересылка. …
Pic.9
Пирамидальная сортировка (HeapSort) Пирамидальная сортировка (HeapSort) Первый этап. Построение пира
Пирамидальная сортировка (HeapSort) Пирамидальная сортировка (HeapSort) Первый этап. Построение пирамиды из элементов массива. В соответствии со свойством 3 правая часть массива уже пирамида. Будем …
Pic.10
| L := n/2 | L := n/2 | DO ( L>0 ) 1 | Построение пирамиды (L, n) | L := L-1 | OD | R := n |
| L := n/2 | L := n/2 | DO ( L>0 ) 1 | Построение пирамиды (L, n) | L := L-1 | OD | R := n | DO ( R>1) 2 | a1↔aR | R := R-1 | Построение пирамиды (1, R) | OD
Pic.11
1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 К У Р А П О В А П О В А А П О В А Р А П О В А В А П О Р А У В А П О
1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 К У Р А П О В А П О В А А П О В А Р А П О В А В А П О Р А У В А П О Р А А В У П О Р А А В А П О Р У К А В А П О Р У А К В А П О Р У А А В К П О Р У
Pic.12
1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 А А В К П О Р У У А В К П О Р А А У В К П О Р А К В У П О Р Р К В У
1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 А А В К П О Р У У А В К П О Р А А У В К П О Р А К В У П О Р Р К В У П О А В К Р У П О В К О У П Р Р К О У П В К Р О У П К П О У Р
Pic.13
Р П О У К Р П О У К О П Р У У П Р О П У Р Р У П Р У У Р У Р П О К В А A
Р П О У К Р П О У К О П Р У У П Р О П У Р Р У П Р У У Р У Р П О К В А A
Pic.14
Трудоемкость пирамидальной сортировки (HeapSort) Трудоемкость пирамидальной сортировки (HeapSort) Оц
Трудоемкость пирамидальной сортировки (HeapSort) Трудоемкость пирамидальной сортировки (HeapSort) Оценим трудоемкость сортировки, используя уже известную оценку трудоемкости построения пирамиды: C = …
Pic.15
«Пирамидальная сортировка HeapSort. Пирамида Хеопса», слайд 15


Скачать презентацию

Если вам понравился сайт и размещенные на нем материалы, пожалуйста, не забывайте поделиться этой страничкой в социальных сетях и с друзьями! Спасибо!