Участник:Shersh/Тикеты по конспектам year2013

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

• Амортизационный анализ
• Саморасширяющийся массив
• Массив с увеличением/уменьшением размера
• Список
• Стек
• Очередь
• Персистентный стек
• Персистентная очередь
• Персистентный дек
• Мажорирующий элемент
• Счетчик Кнута

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

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

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

• Наивные реализации
• Списки с весовой эвристикой
• Реализация с помощью леса корневых деревьев

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

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

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

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

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

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

Хеширование

• Хеш-таблица
• Разрешение коллизий
• Хеширование кукушки
• Идеальное хеширование
• Перехеширование. Амортизационный анализ
• Фильтр Блума
• Универсальное семейство хеш-функций

Сортировка

• Сортировка выбором
• Сортировка пузырьком
• Сортировка вставками
• Сортировка Шелла
• Сортировка кучей
• Быстрая сортировка
• Сортировка слиянием
• Cортировка слиянием с использованием O(1) дополнительной памяти
• Теорема о нижней оценке для сортировки сравнениями
• Сортировка подсчетом
• Сортировка подсчетом сложных объектов
• Цифровая сортировка
• Карманная сортировка
• Поиск k-ой порядковой статистики
• Поиск k-ой порядковой статистики за линейное время
• Сортировка Хана
• Timsort

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

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

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

• Целочисленный двоичный поиск
• Вещественный двоичный поиск
• Троичный поиск
• Поиск с помощью золотого сечения
• Интерполяционный поиск