/semester-work-fibonacci-heap

Primary LanguageC++MIT LicenseMIT

Fibonacci heap

CMake

Краткое описание семестрового проекта :

  • Фибоначчиева куча (англ. Fibonacci heap) — структура данных, отвечающая интерфейсу priority queue. Имеет меньшую амортизированную сложность, чем такие приоритетные очереди как биномиальная куча и двоичная куча.

  • Фибоначчиева куча представляет собой набор фибоначчиевых деревьев

    (прим. Фибоначчиево дерево – это k-ичное дерево, для каждого элемента которого выполняется правило: «дочерний элемент не превышает своего родителя». Корни фибоначчиевых деревьев хранятся в виде кольцевого списка. Каждый узел фибоначчиева дерева, помимо указателей на левого, правого брата, на родителя и на одного из своих сыновей содержит информацию о количестве дочерних узлов.)

Пример:

img.png

  • Фибоначчиевыкучи нашли широкое применение в алгоритмах на графах(поиск минимального остовногодерева, поиск кратчайшего пути в графе)

  • Основные операции:

    • Поиск минимального элемента (getMinimum)
    • Добавление нового элемента (insert)
    • Объединение двух фибоначчиевых куч (merge)
    • Удаление минимального элемента (removeMinimum)
    • Изменение элемента (decreaseKey)

Теоритическая сложность операций

Операция Амортизированная сложность
insert O(1)
getMinimum O(1)
merge O(1)
removeMunimum O(log n)
decreaseKey O(1)

Команда "Fibonacci team"

Фамилия Имя Вклад (%) Прозвище
Ибаев Даниль 50 Биба
Анастасия Войтенко 50 Боба

Девиз команды

Биба и Боба - два...

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

Проект состоит из следующих частей:

  • src/include - реализация структуры данных (исходный код и заголовочные файлы);
  • benchmark - контрольные тесты производительности структуры данных (операции добавления, удаления, поиска и пр.);
  • dataset - наборы данных для запуска контрольных тестов и их генерация;

Требования (Prerequisites)

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

  1. С++ компилятор c поддержкой стандарта C++17 (например, GNU GCC 8.1.x и выше).
  2. Система автоматизации сборки CMake (версия 3.12.x и выше).
  3. Интерпретатор Python (версия 3.7.x и выше).
  4. Рекомендуемый объем оперативной памяти - не менее 8 ГБ.
  5. Свободное дисковое пространство объемом ~ 3 ГБ (набор данных для контрольных тестов).

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

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

Пример (Windows)

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

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

git clone https://github.com/Algorithms-and-Data-Structures-2021/semester-work-fibonacci-heap.git

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

Тестовые наборы данных в формате comma-seperated values (CSV):

# Входные данные для тестов находятся в папке 
cd dataset/data

Тестовые данные представлены в CSV формате (см. \dataset\data\insert\01\100.csv):

39
80
21
...

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

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

Список контрольных тестов
Название Описание Метрики
benchmark_merge объединение двух куч время
benchmark_insert добавление элементов в структуру данных время
benchmark_remove удаление минимального элемента время
Примеры запуска
№ Шаг Файл
1 Перейдите в папку с контрольными тестами benchmark
2 В папке есть 3 файла с контрольными тестами. Перейдите в один из файлов benchmark_insert.cpp benchmark_merge.cpp benchmark_remove.cpp
3 Запустите метод main()
4 После прогона контрольных тестов в папке result появятся 3 файла с результатами тестов benchmark_insert_result.csv benchmark_merge_result.csv benchmark_remove_result.csv

В файлы записываются 4 числа через запятую:

1)номер папки входных данных

2)количество входных данных

3)номер прогона

4)время(в нс)

Источники

Список использованных при реализации структуры данных источников: