Структуры данных

Тематический план

• 

  Тема 1

  Стеки, очереди, деки, списки, кольца 

  • Подборка теории по теме Стек Гиперссылка
  • Теоретический материал: списки (Паскаль) Книга
  • Теоретический материал: стеки, очереди, кольца (Паскаль) Книга
  • Теоретический материал: стеки, очереди, деки (С++) Книга
  • Условия задач
  • Условия задач
  • Теоретический материал: стеки, очереди, деки, динамически расширяемый массивы, списки Файл
• 

  Тема 2

  Куча и приоритетная очередь

  • Теоретический материал - кратко Файл
  • Реализация двоичной кучи Книга
  • Реализация биномиальной кучи Книга
  • 
    Двоичная куча, приоритетная очередь и пирамидальная сортировка - подробно (теоретический материал и задачи):
  • По 1 стр. на листе Файл
  • Для распечатки по 2 стр. на листе Файл
  • Условия задач
• 

  Тема 3

  Двоичное дерево поиска

  • Теоретический материал: двоичное дерево поиска Файл
  • Реализация Книга
  • Условия задач
• 

  Тема 4

  Декартово дерево

  • Теоретический материал Книга
  • Реализация Книга
  • Статья про декартово дерево на хабре (в трёх частях) Гиперссылка
  • Условия задач
• 

  Тема 5

  Структуры данных, оптимизирующие запросы на интервалах (RMQ, RSQ, ...)

  • RMQ: условия задач
  • Дерево интервалов: визуализатор Гиперссылка
• 

  Тема 6

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

  • Теоретический материал Книга
  • Реализация Книга
  • Дерево Фенвика (М.Иванов) Гиперссылка
• 

  Тема 7

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

  • Система непересекающихся множеств (М.Иванов) Гиперссылка
  • Алгоритм Крускала за О(M log N) (М.Иванов) Гиперссылка
  • LCA: алгоритм Тарьяна (М.Иванов) Гиперссылка
  • Условия задач
• 

  Тема 8

  Хеширование

  • Условия задач
  • Теоретический материал: хеширование Файл
• 

  Тема 9

  sqrt-декомпозиция

  • SQRT-декомпозиция. Постановка задачи и реализация Страница
  • SQRT-декомпозиция. Прочие задачи Страница
  • SQRT-декомпозиция входных запросов Страница
  • Эвристика для некоторых типов задач Страница
  • Условия задач
  • sqrt-декомпозиция (М.Иванов) Гиперссылка
• 

  Тема 10

  sparse table (разреженная таблица)

  • Теоретический материал (М.Ахмедов) Гиперссылка