Реклама
Комментарии 5

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

Мне больше нравиться название метод «царь горы» оно сразу объясняет как это работает. А вот слово «просейка» — как-то мало информативно.
Царь горы — максимум в корне — это уже конечный результат многократной просейки. А единичная просейка не столько направлена на поднятие максимума вверх, сколько на то, чтобы скинуть мелочь как можно ниже.
N-арный heapsort будет обгонять простой heapsort, если стоимость операций:
взять соседний элемент на том же уровне N или взять на уровне выше/ниже (N±1) будет разной. Например если дерево на диске, а соседние элементы лежат физически в одном блоке. Тогда чем выше N, тем более быстрорастущим будет дерево и тем больше будет скорость сортировки. Здесь полная аналогия с бинарным и B-деревом.
Только полноправные пользователи могут оставлять комментарии. , пожалуйста.