Структуры данных (28 сентября 2016)

1. [15 минут] Хеш-таблица
1. Чем хеш-таблица лучше масива? поиск и удаление за O(1).
2. Умеем Add, Del, Find. Интерфейсы HashSet, HashMap. Решение задачи про два указателя хеш-таблицей.
3. Открытая адресация: i = hash(x), while (h[i] && h[i] != x) i++;
4. Сравнение открытой и списков: открытая быстрее, из списков проще удалять. Удаление из открытой: просто помечаем, когда помеченных слишком много, перестроим таблицу.
2. [20 минут] Избавляемся от амортизации:
1. Вектор. Ленивое копирование: когда переполнились начинаем копировать по одному элементу
2. Вектор. Ленивое копирование: заранее начинаем копировать по одному элементу и выделять память
3. Хеш-таблица. Ленивое копирование.
4. Очередь с минимумом на двух стеках. Реализация через два динамических массива.
3. [25 минут] Куча
1. Интерфейс, преобразование функций друг через друга: Add, Del, ExtractMin, DecreaseKey
2. Бинарная куча: реализация на массиве через siftUp → decreaseKey, Add; siftDown → Del
3. Бинарная куча: build за O(n) (док-во sum k/2^k уже было в практике)
4. Обратные ссылки (пример: массив с операцями a[i]=x, min на всём массиве)
5. Min = Max (+1 на -1, меньше на больше)
6. heapsort = build + ExtractMin*n

1. [30 минут] Аллокация памяти:
1. сложность задачи, пример решения: heap + hash_table
2. стек + рекурсия, c++: рекурсия с финализатором и примером рекурсивной функции
3. список + куски одного размера (пример: хеш-таблица на списках) + кеширование
4. в с++ : new, delete = empty