Алгоритмы и структуры данных

Амортизационный анализ

• Амортизационный анализ
• Динамический массив
• Hashed Array Tree[math]^\star[/math]
• Список
• Стек
• Очередь
• Дек
• Мажорирующий элемент
• Счетчик Кнута
• Мастер-теорема[math]^\star[/math]
• List order maintenance[math]^\star[/math]

Персистентные структуры данных

• Персистентные структуры данных
• Персистентный стек
• Персистентная очередь
• Персистентный дек
• Персистентная приоритетная очередь

Приоритетные очереди

• Двоичная куча
• Биномиальная куча
• Фибоначчиева куча
• Левосторонняя куча
• Тонкая куча
• Толстая куча на избыточном счетчике
• Куча Бродала-Окасаки[math]^\star[/math]

Система непересекающихся множеств

• Наивные реализации
• Списки с весовой эвристикой
• Реализация с помощью леса корневых деревьев
• СНМ с операцией удаления за О(1)[math]^\star[/math]

Поисковые структуры данных

• Упорядоченное множество
• Дерево поиска, наивная реализация
• АВЛ-дерево
• 2-3 дерево
• B-дерево
• Красно-черное дерево
• Декартово дерево
• Декартово дерево по неявному ключу
• Splay-дерево
• Взвешенное дерево
• Tango-дерево[math]^\star[/math]
• Рандомизированное бинарное дерево поиска
• Дерево ван Эмде Боаса
• Список с пропусками
• Fusion tree[math]^\star[/math]
• Сверхбыстрый цифровой бор
• Rope[math]^\star[/math]
• AA-дерево[math]^\star[/math]

Дерево отрезков

• Статистики на отрезках. Корневая эвристика
• Корневая декомпозиция с операциями: get, insert, erase
• Дерево отрезков. Построение
• Реализация запроса в дереве отрезков сверху
• Реализация запроса в дереве отрезков снизу
• Несогласованные поддеревья. Реализация массового обновления
• Многомерное дерево отрезков
• Сжатое многомерное дерево отрезков

Дерево Фенвика

• Дерево Фенвика
• Встречное дерево Фенвика
• Дерево Фенвика для некоммутативных операций
• Многомерное дерево Фенвика

Хеширование

• Хеш-таблица
• Разрешение коллизий
• Хеширование кукушки
• Идеальное хеширование
• Перехеширование
• Фильтр Блума
• Quotient filter[math]^\star[/math]
• Универсальное семейство хеш-функций
• Расширяемое хеширование[math]^\star[/math]

Сортировки

Квадратичные сортировки

• Сортировка выбором
• Сортировка пузырьком
• Сортировка вставками

Сортировки на сравнениях

• Сортировка Шелла[math]^\star[/math]
• Сортировка кучей
• Быстрая сортировка
• Сортировка слиянием
• Cортировка слиянием с использованием O(1) дополнительной памяти
• Терпеливая сортировка[math]^\star[/math]
• Timsort[math]^\star[/math]
• Smoothsort[math]^\star[/math]
• Теорема о нижней оценке для сортировки сравнениями

Многопоточные сортировки

• Многопоточная сортировка слиянием[math]^\star[/math]
• PSRS-сортировка[math]^\star[/math]

Другие сортировки

• Поиск k-ой порядковой статистики
• Поиск k-ой порядковой статистики за линейное время
• Поиск k-ой порядковой статистики в двух массивах[math]^\star[/math]
• Сортировка подсчетом
• Цифровая сортировка
• Карманная сортировка
• Сортировка Хана[math]^\star[/math]
• Задача флага Нидерландов[math]^\star[/math]
• Блинная сортировка[math]^\star[/math]

Сортирующие сети

• Сортирующие сети
• Проверка сети компараторов на то, что она сортирующая. 0-1 принцип
• Сортирующие сети для квадратичных сортировок
• Сортировочные сети с особыми свойствами[math]^\star[/math]
• Сеть Бетчера

Алгоритмы поиска

• Целочисленный двоичный поиск
• Поиск в матрице[math]^\star[/math]
• Вещественный двоичный поиск
• Троичный поиск
• Поиск с помощью золотого сечения
• Интерполяционный поиск
• Метод Фибоначчи[math]^\star[/math]

Связь между структурами данных

• Связь между структурами данных