Комментарии 5
Кроме асимптотических оценок хорошо было бы сравнить реальное время операций для разных куч на тестовом наборе данных, скажем, для 100, 1000, 10000 и 100000 элементов, а так же объем служебных данных на один элемент.
Согласен. На выходных постараюсь добавить сравнение с основным конкурентом (Куча Фибоначчи) и популярной Бинарной кучей
2-3 куча — не очень благодарный объект для реализации, поэтому я сравнивал только бинарную и фибоначчиеву кучи.
Было три теста.
1) N^2 операций «добавить элемент — уменьшить ключ — удалить минимальный элемент» примерно в равных количествах.
2) N добавлений элементов, N^2/2 случайных уменьшений ключа, N удалений минимального элемента
3) N добавлений элементов, N^2/2 «самых плохих» уменьшений ключа — когда наибольший ключ заменяется на величину, меньшую, чем все имеющиеся, N удалений минимального элемента.
Результаты (время на один тест, в миллисекундах):
Было три теста.
1) N^2 операций «добавить элемент — уменьшить ключ — удалить минимальный элемент» примерно в равных количествах.
2) N добавлений элементов, N^2/2 случайных уменьшений ключа, N удалений минимального элемента
3) N добавлений элементов, N^2/2 «самых плохих» уменьшений ключа — когда наибольший ключ заменяется на величину, меньшую, чем все имеющиеся, N удалений минимального элемента.
Результаты (время на один тест, в миллисекундах):
Test1: N Binary Fibonaccy
1000 59.0 147
3000 627 1554
10000 9551 19125
30000 103710 182688
50000 310197 567197
Test2: N Binary Fibonaccy
1000 10.1 12.0
3000 95.8 128
10000 1206 1605
30000 11814 15148
50000 32147 46705
Test3: N Binary Fibonaccy
1000 11.2 14.6
3000 132 135
10000 1904 1520
30000 21719 13751
50000 68438 41845
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Структуры данных: 2-3 куча (2-3 heap)