Пирамиды

[fat_crocodile]

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

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

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

Comments

[plumqqz]

Скорее всего, не раньше, чем это станет статьёй.

Гонорары - дело, разумеется, богоугодное, но неужели кто-то готов публиковать статьи по этой, мягко говоря, глубоко обсосанной со всех сторон теме?

[fat_crocodile]

Гусары денег не берут.
Нормальная статья отличается некоторыми мелочами и количеством потраченного на неё времени - я сейчас не могу столько выделить.

Обоссанной... Ты знаешь, куда не плюнь - почти всё уже обоссали. Но как-то так получается, что обоссать каждый может, а внятно изложить - очень редкий экземпляр. Я могу.

обСОСанный

[plumqqz]

http://www.google.com/search?ie=UTF-8&hl=ru&q=%D0%BF%D0%B8%D1%80%D0%B0%D0%BC%D0%B8%D0%B4%D0%B0%20%D0%BE%D1%87%D0%B5%D1%80%D0%B5%D0%B4%D1%8C%20%D1%81%20%D0%BF%D1%80%D0%B8%D0%BE%D1%80%D0%B8%D1%82%D0%B5%D1%82%D0%B0%D0%BC%D0%B8

Результаты 1 - 10 из примерно 138 000 для пирамида очередь с приоритетами

Полагаешь, что сможешь сделать и свой вклад? Ну, отчего бы и нет, собственно говоря...

Re: обСОСанный

[fat_crocodile]

Это Фрейд, это Фрейд :) Спасибо за поправку.

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

[ran_dom]

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

[fat_crocodile]

Ну да. Я тоже раньше про пирамидальную сортировку только слышал, причём слышал, только что это что-то сложное :) А тут случайно разобрался, так просто оказалось.

[scavenger_spb]

Все становится просто после того, как разберешься.

[fat_crocodile]

Да, но в данном случае оказалось, что просто не только разобраться, но просто и объяснить. Не требуется ни какой особой подготовки, ни упоминания каких-то сторонних концепций.. То есть я просто не вижу ни одного повода, почему этот алгоритм можно считать сложным.

[kodt_rsdn]

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

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

[fat_crocodile]

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

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

[kodt_rsdn]

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

[fat_crocodile]

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