Пирамиды

[fat_crocodile]

Когда-нибудь это будет маленькая но гордая статья, пока - так.

Ты моя мумия, я твоя пирамида

Пирамида это дерево. Не обязательно двоичное - любое. Листья и узлы это некие "элементы", на которых определены операции сравнения (<>=). И единственное условие на пирамиду - узел должен быть меньше-или-равен каждого из своих детей

Comments

[kodt_rsdn]

Это ты рассказал про фиксированно-арные пирамиды, а картинки нарисовал - вообще бинарные.

А как насчёт навороченных пирамид - биномиальной и фибоначчиевой?
Там уже не так просто отобразить пирамиду на массив, не потеряв главное достоинство - быструю вставку.

[fat_crocodile]

В псевдографике сложно нарисовать пирамиды большей арности :) Да и понимать с этими проще.

А биномиальные-фибоначчивые - зачем нужны и где почитать?

[kodt_rsdn]

Как ни странно, в гугле и википедии (binomial heap, fibonacci heap), не говоря уже про Кормена.
У них более дешёвые операции слияния. Частным случаем которого является слияние с кучей нулевого ранга, состоящей из единственного элемента.

[fat_crocodile]

Ок. Я про них просто не знал. Ну пусть будут...
Только мне сначала надо Ахо-Ульмана-Сети до середины хотя бы дочитать :)

*хвастаюсь* :)

[fat_crocodile]

Кстати, в коде сортировки (которую я всё-таки написал, но пока не выложил) арность задаётся параметром шаблона. У меня лучшие результаты получились при восьми детях.

Re: *хвастаюсь* :)

[kodt_rsdn]

Возможно, что это связано с кэшем и с более простыми предсказаниями переходов.
На очень маленьких массивах, как известно, сортировка вставками рвёт быструю.

Re: *хвастаюсь* :)

[fat_crocodile]

Я предположил, что это момент, когда k*logkN (из алгоритма опускания) минимален.

А по сравнению с квиксортом они все отстают раз в шесть-восемь.

Размер массива - 1-10-100 миллионов интов.

Re: *хвастаюсь* :)

[fat_crocodile]

да, напрасно я это предположил... Посчитать несложно.

Но, с другой стороны, процесс сбора пирамиды честно ускоряется без всяких накладных расходов. Так что в сумме минимум для 100 миллионов получается в четвёрке.