Comments 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
Only those users with full accounts are able to leave comments. Log in, please.
Структуры данных: 2-3 куча (2-3 heap)