Структуры данных: 2-3 куча (2-3 heap)

[dyadyaSerezha]

Кроме асимптотических оценок хорошо было бы сравнить реальное время операций для разных куч на тестовом наборе данных, скажем, для 100, 1000, 10000 и 100000 элементов, а так же объем служебных данных на один элемент.

[biziwalker]

Согласен. На выходных постараюсь добавить сравнение с основным конкурентом (Куча Фибоначчи) и популярной Бинарной кучей

[Mrrl]

2-3 куча — не очень благодарный объект для реализации, поэтому я сравнивал только бинарную и фибоначчиеву кучи.
Было три теста.
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

[dyadyaSerezha]

Я правильно понял, что для Фибоначчи третий, наихудший тест, даёт лучшую производительность по сравнению с собой же, с тестом 2 уже начиная с 10 тыс? Как-то странно.

[Mrrl]

А, это время на работу генератора случайных чисел. Оно занимает до 1/3 работы всего теста — там где случайные числа нужны. В третьем тесте всё детерминированно, поэтому на генераторе удалось сэкономить.