semester-project-binomial-heap

Биномиальная куча — структура данных, реализующая абстрактный тип данных «очередь с приоритетом», которая представляет собой набор биномиальных деревьев с двумя свойствами: ключ каждой вершины не меньше ключа её родителя; все биномиальные деревья имеют разный размер.

Биномиальная куча используется в Дискретном моделировании событий. Дискретно-событийное моделирование (DES) моделирует работу системы как (дискретную) последовательность событий во времени.

Основные операции, производимые над кучей - сложность данных операций:

Вставка элемента в кучу - O(1) - Константная. Слияние двух куч - O(logN) - Логарифмическая. Удаление минимального элемента из кучи - O(logN) - Логарифмическая.

Команда "nurlat"

Группа: 11-109

Фамилия Имя	Вклад (%)	Прозвище
Намаев Альберт	100000	альберт
Тихонов Никита	20	никита
Султанов Тимур	10	тимур
Комелина София	10	софа

Google Drive

https://drive.google.com/drive/folders/1kUNio3z1i3jwlT8Ak_fVOf_0Ziy4kDPC?usp=sharing

Требования

В этом разделе задаются основые требования к программному и аппаратному обеспечению для успешной работы с вашим проектом.

Пример. Рекомендуемые требования:

1. Интерпретатор Python (версия 3.7.x и выше).
2. Рекомендуемый объем оперативной памяти - не менее 8 ГБ.
3. Свободное дисковое пространство объемом ~ 2 ГБ (для входного набора данных).

Сборка и запуск

Здесь можно оставить ссылку с видео-инструкцией по сборке и запуску проекта.

Пример (Windows)

Сборка проекта

Опишите процесс сборки проекта.

Склонируйте проект к себе на устройство через Git for Windows (либо используйте возможности среды разработки):

git clone https://github.com/Algorithms-and-Data-Structures-2022/semester-work-template.git

Сборка и запуск проекта осуществляется через среду разработки.

Генерация тестовых данных

Опишите формат хранения (JSON, XML, CSV, YAML и т.д.) и процесс генерации тестовых данных.

Разрешается использовать собственный формат хранения данных.

Пример. Генерация тестового набора данных

Формат данных: comma-seperated values (CSV).

Инструкции по генерации:

# переход в папку генерации набора данных
cd dataset

# запуск Python-скрипта
python generate_csv_bench_dataset.py --samples 1000 <output> [args ...]

• --samples - количество генерируемых элементов;
• <output> - выходной файл и т.д.

Тестовые данные представлены в CSV формате (см.

id, full_name
0, "Ramil Safin"
1, "Bulat Abbyasov"
...

Примечание. Для удобства запуска контрольных тестов рекомендуется организовывать данные в директориях, например:

dataset/data/
  add/
    01/
      100.csv
      ...
      5000000.csv
    02/ ...
    03/ ...
    ...
    10/ ...
  search/
    01/
      100.csv
      ...
      5000000.csv
    ...
    10/ ...
  ...

По названию директории /dataset/data/add можно понять, что здесь хранятся наборы данных для контрольных тестов по добавлению элементов в структуру данных. Названия файлов 100.csv. 5000000.csv и т.д. хранят информацию о размере набора данных (т.е. количество элементов).

Контрольные тесты (benchmarks)

Опишите, как запустить контрольные тесты, что они из себя представляют, какие метрики замеряют (время работы, потребление памяти и пр.).

Пример. Для запуска контрольных тестов необходимо предварительно сгенерировать или скачать готовый набор тестовых данных.

Примечание. Во избежание "захламления" репозитория большим объёмом данных рекомендуется указать ссылку на архив с набором данных, который при необходимости можно скачать по ссылке.

Список контрольных тестов

Название	Описание	Метрики
search_benchmark	поиск элементов	время
add_benchmark	добавление элементов в структуру данных	время, память
...	...	...

Примеры запуска

./benchmark <input> <output> --trials 50

• <input> - входной файл с набором данных в формате CSV;
• <output> - выходной файл с результатами контрольного теста;
• --trials - количество прогонов на наборе данных и т.д.

Добавление 10000 случайных элементов в структуру данных (повторить операцию 50 раз и вычислить среднее время работы и потребляемую память):

./add_benchmark.exe ../dataset/data/add/10000.csv metrics.txt --trials 50

где <input> = ../dataset/data/add/10000.csv и <output> = metrics.txt.

Источники

Список использованных при реализации структуры данных источников. https://en.wikipedia.org/wiki/Binomial_heap

http://www.cs.unc.edu/~bbb/#binomial_heaps

https://github.com/brandenburg/binomial-heaps/blob/master/bh.py

http://cppalgo.blogspot.com/2011/05/binomial-queue.html

Это не плагиат, это уважение чужого труда и помощь своим сокурсникам более подробно разобраться в теме.