Структуры и алгоритмы компьютерной обработки данных

Федеральное государственное автономное образовательное учреждение высшего образования «САНКТ-ПЕТЕРБУРГСКИЙ ПОЛИТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ ПЕТРА ВЕЛИКОГО» Институт компьютерных наук и технологий Высшая школа интеллектуальных систем и суперкомпьютерных технологий В.Г. Пак Структуры и алгоритмы компьютерной обработки данных Слайды видеолекций для студентов бакалавриата направлений подготовки высшего образования «Математическое обеспечение и администрирование информационных систем» и «Прикладная информатика» Санкт-Петербургский политехнический университет Петра Великого 2020 Санкт-Петербургский политехнический университет Петра Великого, 2020 © Федеральное государственное автономное образовательное учреждение высшего образования «САНКТ-ПЕТЕРБУРГСКИЙ ПОЛИТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ ПЕТРА ВЕЛИКОГО» Институт компьютерных наук и технологий Высшая школа интеллектуальных систем и суперкомпьютерных технологий ЛЕКЦИЯ №5 Пирамидальная сортировка на сбалансированных деревьях. Внешняя сортировка Санкт-Петербургский политехнический университет Петра Великого 2020 Санкт-Петербургский политехнический университет Петра Великого, 2020 © Содержание IV. Алгоритмы сортировки §2. Алгоритмы внутренней сортировки 2.4. Пирамидальная сортировка на сбалансированных деревьях 2.4.1. Основные операторы АТД множеств 2.4.2. Реализация АТД множеств с помощью сбалансированных деревьев 2.4.3. Операторы АТД множеств на сбалансированных деревьях 2.4.4. Алгоритм пирамидальной сортировки на сбалансированных деревьях Структуры и алгоритмы компьютерной обработки данных Лекция 5. Пирамидальная сортировка. Внешняя сортировка 3 Содержание (окончание) 2.5. Пирамидальная сортировка на частично упорядоченных деревьях 2.5.1. Реализация АТД очередей с приоритетами с помощью частично упорядоченных деревьев 2.5.2. Алгоритм пирамидальной сортировки на частично упорядоченных деревьях Структуры и алгоритмы компьютерной обработки данных Лекция 5. Пирамидальная сортировка. Внешняя сортировка 4 Содержание §3. Алгоритмы внешней сортировки 3.1. Модель внешней обработки данных 3.2. Внешняя сортировка слиянием 3.3. Многоканальное слияние 3.4. Многофазная сортировка Структуры и алгоритмы компьютерной обработки данных Лекция 5. Пирамидальная сортировка. Внешняя сортировка 5 2.4.1. Основные операторы АТД множеств Следующий быстрый алгоритм, который будет изучен, - пирамидальная сортировка. Он имеет вычислительную сложность Ο 𝑛 log 𝑛 и худшем, и в среднем. Его можно записать в абстрактной форме, используя операторы АТД множеств. 2.4. Пирамидальная сортировка на сбалансированных деревьях 2.4.1. Основные операторы АТД множеств Здесь будут рассмотрены используемые в алгоритме операторы АТД множеств и некоторые реализации множеств. 1. Процедура INSERT(x, A), где элемент 𝑥 имеет тот же тип данных, что и элементы 𝐴. Процедура делает 𝑥 элементом 𝐴, т.е. INSERT(x, A)=𝐴 ∪ 𝑥 . Структуры и алгоритмы компьютерной обработки данных Лекция 5. Пирамидальная сортировка. Внешняя сортировка 6 2.4.1. Основные операторы АТД множеств 2. Процедура DELETE(x, A), где элемент 𝑥 имеет тот же тип данных, что и элементы 𝐴. Процедура удаляет 𝑥 из 𝐴, т.е. DELETE(x, A)=𝐴\ 𝑥 . 3. Функция MIN(A) возвращает минимальный элемент 𝐴. Для применения необходимо, чтобы на элементах 𝐴 был определѐн линейный порядок. 4. Функция MAX(A) возвращает максимальный элемент 𝐴. 5. Функция EMPTY(A) возвращает true, если 𝐴 = ∅, false в противном случае. 6. Процедура DELETEMIN(A) находит минимальный элемент 𝐴 и удаляет его из 𝐴, т.е. DELETEMIN(A)=𝐴\ min 𝐴 . 7. Процедура DELETEMAX(A) находит максимальный элемент 𝐴 и удаляет его из 𝐴, т.е. DELETEMAX(A)=𝐴\ max 𝐴 . Структуры и алгоритмы компьютерной обработки данных Лекция 5. Пирамидальная сортировка. Внешняя сортировка 7 2.4.2. Реализация АТД множеств с помощью сбалансированных деревьев 2.4.2. Реализация АТД множеств с помощью сбалансированных деревьев Пример реализации АТД структурой данных, позволяющей выполнять операторы за время порядка Ο log 𝑛 . Сбалансированное дерево – дерево, в котором высота поддеревьев любого узла различается не более чем на заданную величину k. Виды сбалансированных деревьев: • АВЛ-деревья (Адельсон-Вельский, Ландис); • красно-чѐрные деревья; • B-деревья; • … АВЛ-дерево – сбалансированное двоичное дерево, в котором у любого внутреннего узла высота левого и правого поддеревьев отличаются не более чем на единицу. Известно, что алгоритмы поиска, вставки и удаления на АВЛ-деревьях имеют вычислительную сложность Ο log 𝑛 в среднем и в худшем. Структуры и алгоритмы компьютерной обработки данных Лекция 5. Пирамидальная сортировка. Внешняя сортировка 8 2.4.2. Реализация АТД множеств с помощью сбалансированных деревьев Построим реализацию АТД множеств, в которой операторы имеют время выполнения в худшем случае Ο log 𝑛 . Сбалансированное дерево является 2-3-деревом, если в нѐм: 1. Каждый внутренний узел имеет либо 2, либо 3 сыновей. 2. Все пути от корня до любого листа имеют одинаковую длину. Пустое дерево Λ и дерево из одного корня также являются 2-3деревьями. Реализуем множества, упорядоченные отношением линейного порядка < (не ≤, т.к. нет одинаковых элементов), 2-3-деревьями следующим образом. Элементы множества располагаются в листах дерева, причѐм, если 𝑎 < 𝑏, то 𝑎 находится левее 𝑏 и наоборот. Внутренний узел Наименьший элемент, являющийся потомком второго сына 𝑦 𝑧 Наименьший элемент, являющийся потомком третьего сына Структуры и алгоритмы компьютерной обработки данных Лекция 5. Пирамидальная сортировка. Внешняя сортировка 9 2.4.2. Реализация АТД множеств с помощью сбалансированных деревьев Любое 2-3-дерево с 𝑘 уровнями имеет от 2𝑘−1 до 3𝑘−1 листьев, значит, дерево, реализующее (𝑛)-множество, будет иметь от 1 + log 2 𝑛 до 1 + log 3 𝑛 уровней. Следовательно, длины всех путей имеют порядок Ο log 𝑛 . Элемент 𝑥 находится в представляющем множество 𝐴 2-3дереве за время порядка Ο log 𝑛 следующим перемещением по дереву: 1. Во внутреннем узле 𝑥 сравнивается с 𝑦. Структуры и алгоритмы компьютерной обработки данных Лекция 5. Пирамидальная сортировка. Внешняя сортировка 10 2.4.2. Реализация АТД множеств с помощью сбалансированных деревьев Внутренний узел Да 𝑥<𝑦 перемещаемся к 1-му сыну узла Да Да перемещаемся ко 2-му сыну узла Нет узел имеет 3 сыновей Нет перемещаемся ко 2-му сыну узла 𝑥 𝑝. Структуры и алгоритмы компьютерной обработки данных Лекция 5. Пирамидальная сортировка. Внешняя сортировка 38 3.4. Многофазная сортировка • Поскольку число записей в исходном файле может не обеспечить такого распределения, применяется метод добавления пустых записей (серий), которые в дальнейшем как можно более равномерно распределяются между промежуточными файлами. Понятно, что чем меньше таких пустых серий, т.е. чем ближе число сортируемых записей к суммам чисел Фибоначчи, тем более эффективно работает алгоритм. Структуры и алгоритмы компьютерной обработки данных Лекция 5. Пирамидальная сортировка. Внешняя сортировка 39