Pull to refresh

Comments 5

Число потомков хорошо подобрать по размеру кеш линии, которая для x86 64 байта. Соответственно если сравнивать просто 32битные ключи, то n=16. Для 64х битных уже 8. Простые сравнения чисел намного быстрее промахов кэша.

Отличный материал. Не пожалел времени на чтение.
Мне больше нравиться название метод «царь горы» оно сразу объясняет как это работает. А вот слово «просейка» — как-то мало информативно.
Царь горы — максимум в корне — это уже конечный результат многократной просейки. А единичная просейка не столько направлена на поднятие максимума вверх, сколько на то, чтобы скинуть мелочь как можно ниже.
N-арный heapsort будет обгонять простой heapsort, если стоимость операций:
взять соседний элемент на том же уровне N или взять на уровне выше/ниже (N±1) будет разной. Например если дерево на диске, а соседние элементы лежат физически в одном блоке. Тогда чем выше N, тем более быстрорастущим будет дерево и тем больше будет скорость сортировки. Здесь полная аналогия с бинарным и B-деревом.
Only those users with full accounts are able to leave comments. Log in, please.