Комментарии 5
Число потомков хорошо подобрать по размеру кеш линии, которая для x86 64 байта. Соответственно если сравнивать просто 32битные ключи, то n=16. Для 64х битных уже 8. Простые сравнения чисел намного быстрее промахов кэша.
+2
Отличный материал. Не пожалел времени на чтение.
+3
Мне больше нравиться название метод «царь горы» оно сразу объясняет как это работает. А вот слово «просейка» — как-то мало информативно.
+2
N-арный heapsort будет обгонять простой heapsort, если стоимость операций:
взять соседний элемент на том же уровне N или взять на уровне выше/ниже (N±1) будет разной. Например если дерево на диске, а соседние элементы лежат физически в одном блоке. Тогда чем выше N, тем более быстрорастущим будет дерево и тем больше будет скорость сортировки. Здесь полная аналогия с бинарным и B-деревом.
взять соседний элемент на том же уровне N или взять на уровне выше/ниже (N±1) будет разной. Например если дерево на диске, а соседние элементы лежат физически в одном блоке. Тогда чем выше N, тем более быстрорастущим будет дерево и тем больше будет скорость сортировки. Здесь полная аналогия с бинарным и B-деревом.
+2
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Сортировка n-нарной пирамидой