Поразрядная LSD - сортировка. Лекция 5

Поразрядная LSD - сортировка

Поразрядная LSD - сортировка

Поразрядная LSD - сортировка
LSD-сортировка
цикл для i от 0 до D нц
|| D – количество разрядов ключа
Сортировка разряда i
кц
конец
Сортировка не рекурсивная

Очереди по приоритетам
Во многих приложениях требуется обработка записей с упорядоченными определенным образом ключами:
не обязательно в строгом порядке;
не обязательно всех сразу.
накапливается набор записей
обрабатывается запись с максимальным ключом
накапливается набор записей
обрабатывается запись с максимальным ключом

Структура данных, поддерживающая операции
вставки нового элемента;
удаления элемента с максимальным значением ключа
называется
очередью по приоритетам.
Очереди по приоритетам

• Системы моделирования – каждое событие системы характеризуется моментом возникновения, это помогает обслуживать события в хронологическом порядке.
• Системы планирования заданий в вычислительных системах – приоритет указывает, какая задача должна выполнятся первой
• Численные расчеты – приоритет (ошибка), наиболее грубые ошибки должны исправляться первыми.
Очереди по приоритетам

На практике очереди по приоритетам более сложны:
• создать очередь по приоритетам из N заданных элементов;
• изменить приоритет произвольного элемента;
• удалить произвольный элемент;
• объединить две очереди по приоритетам в одну.
Очереди по приоритетам

Базовые структуры для очереди:
односвязный список,
двусвязный список
массив.
Каждая из описанных процедур может быть реализована различными способами, в зависимости от конкретной решаемой задачи.
Очереди по приоритетам

Процедура вставки
Вставлять элемент в начало очереди.
Вставлять элемент в конец очереди.
Вставлять элемент в заданное место.
Очереди по приоритетам
Процедура удаления элемента с наибольшим ключом
Найти элемент с максимальным ключом и переставить его в конец. Удалить элемент.
Найти элемент с максимальным ключом и сразу удалить его.

Упорядоченные последовательности элементов
Процедура вставки требует просмотра всей последовательности элементов - O(n). Процедура удаления и поиска максимального выполняется за постоянное время - O(1).
Очереди по приоритетам

Неупорядоченные последовательности
Процедура вставки выполняется за постоянное время – O(1).
Процедура удаления и поиска требует просмотра всей последовательности – O(n).
Очереди по приоритетам
Подходы к организации работы
Ленивый – основная работа откладывается.
Энергичный – основная работа выполняется на этапе подготовки последовательности.

Представление очереди с помощью пирамиды
Частично упорядоченный массив;
в корне дерева (первый элемент массива) находится элемент с наибольшим ключом.
Очереди по приоритетам
Процедура добавления нового элемента
2
7
9
4
5
1
8
3
8
9
Исходный массив

2
7
9
4
5
1
8
3
8
9
Представление очереди пирамидой
10
2
7
9
4
5
1
8
3
8
9
10
2
9
4
5
1
8
3
8
9
10
7
2
9
4
5
1
8
3
8
7
10
9
Добавление нового элемента

Представление очереди пирамидой
Добавление нового элемента
Добавление нового элемента в конец массива.
Передвижение элемента к своему месту.

Представление очереди пирамидой
2
4
5
1
8
3
8
7
9
9
10
Удаление максимального элемента
2
4
5
1
8
3
8
9
9
10
7
2
4
5
1
8
3
8
9
9
7
2
4
5
1
8
3
8
7
9
9

Представление очереди пирамидой
Удаление максимального элемента
Обмен нулевого и последнего элемента
Удаление последнего элемента массива.
Перестройка пирамиды на нулевом элементе.

Представление очереди пирамидой
Изменение приоритета элемента
2
4
5
1
8
3
8
7
9
9
3
2
3
5
1
8
3
4
7
9
8
При уменьшении приоритета – «спуск элемента»
При увеличении приоритета – «подъем» элемента

Биномиальная очередь
(1978 г. Вильемин)
Бинарное дерево называется левосторонним пирамидально упорядоченным, если ключ каждого узла больше или равен всем ключам левого поддерева, если таковое имеется.
2
7
9
4
5
1
8
3
8
9
14
9
10
8
9
11
12
3
7
9

Биномиальная очередь
Сортирующее дерево степени 2 есть левостороннее пирамидально упорядоченное дерево, состоящее из корневого узла с пустым правым поддеревом и полным левым поддеревом.
8
10
7
2
4
8
9
1
Null

Биномиальная очередь
Левый потомок сортирующего дерева степени 2 называется биномиальным деревом.
• Кол-во узлов сортирующего дерева степени 2 есть число степени 2.
• Ни один из ключей не обладает значением, большим ключа корня дерева.
• Биномиальные деревья пирамидально упорядочены.

Биномиальная очередь
Если реализация биномиального дерева выполнена на основе связных структур, то объединение двух деревьев одинакового размера в одно сводится к изменению двух связей.
struct Root {
int d;
Root *left;
Root *rigth; }

Биномиальная очередь
8
10
7
2
4
8
9
1
Null
5
8
2
4
3
4
7
1
Null
Root * r1
Root * r2
Root * temp = r1-> left
r1-> left = r2
r2-> right = temp

Биномиальная очередь
8
10
7
2
4
8
9
1
5
8
2
4
3
4
7
1
Null

Биномиальная очередь
Биномиальная очередь представляет собой набор сортирующих деревьев степени 2 , ни одно из которых не совпадает с другими по размеру.
Структура биномиальной очереди совпадает с единичными разрядами двоичного представления числа узлов этой очереди.
2510 = 110012

Биномиальная очередь
3
5
9
2
2
1
4
4
7
8
Добавление нового элемента
аналог операции +1 10102 + 12 = 10112
7

Биномиальная очередь
Алгоритм добавления нового элемента
проинициализировать новый элемент как 1-дерево переноса
i=0
пока не обнаружится пустая позиция для сортирующего дерева нц
если в очереди есть 2i дерево, то объединить его с i - деревом переноса
записать полученное дерево в дерево 2i+1 переноса.
i=i+1 кц

Биномиальная очередь
3
5
9
2
2
1
4
4
7
8
7
8
5
9
2
2
1
4
7
8
8
4
7
3

Биномиальная очередь
аналог операции -1 10102 - 12 = 10012
3
5
9
2
2
1
4
4
7
8
5
2
2
1
4
7
8
3
4
Удаление максимального элемента

Биномиальная очередь
5
2
2
1
4
7
8
3
4
2
4
7
8
5
2
1
3
4
2
4
7
8
5
3
1
2
4
4
7
5
8
4
2
1
2
3

Биномиальная очередь
Алгоритм удаления элемента
найти дерево 2i в корне которого расположен максимальный элемент.
удалить максимальный элемент
2i дерево разбить на i-1, i-2, … 0 деревья переноса.
i=0
пока не обнаружится пустая позиция для сортирующего дерева нц
если в очереди есть 2i дерево, то объединить его с i - деревом переноса

записать полученное дерево в дерево 2i+1 переноса.
i=i+1 кц
Биномиальная очередь

Биномиальная очередь
Объединение двух очередей
аналог операции + 10102 + 112 = 11012
3
5
9
2
2
1
4
4
7
8
6
3
7