D-hip

$D$ -хип је структура реда са приоритетом, генерализација Бинарног хипа у којој чворови имају $д$ потомака уместо 2.^[1]^[2]^[3] Дакле бинарни хип је уствари 2-хип. Према Тарјан-у^[2] и Јенсен-у,^[4] $д$ -хип је измишљен од стране Доналд Б. Јохнсон још 1975.^[1]

Ова структура података омогућава да операције смањена приоритета буду извршаване брже него у бинарном хипу, по цену успоравања операције за брисање минимума. Ова измена доводи до бржег извршавања алгоритама као сто су Дајкстра алгоритам у ком су операције смањена приоритета чесће него брисања минимума.^[1]^[5] Поред тога, $д$ -хип има и понашање погодније за кеш меморију него бинарни хип, што му омогућава брже извршавање у пракси, без обзира што теориски има шири најгори случај.^[6]^[7] Као и бинарни хип, тако и $д$ -хип ради у месту тј. не користи никакав додатни простор, поред потребног низа елемената за хип.^[2]^[8]

Структура д-хипа[уреди | уреди извор]

$D$ -хип се састоји од низа од $н$ елемената, где се сваком од елемената додељује и приоритет. Ти елементи могу бити представљени као цворови у комплетном $д$ -хип стаблу, излистани помоцу БФС-а : елемент низа на позицији 0 представља корен стабла, елеменати на позицији 1- $д$ представљају децу, следецих $д 2$ су унуци, итд. Дакле, родитељски цвор елемента на позицији $и$ (за свако $и > 0$ ) је елемент на позицији $флоор((и - 1)/ д)$ његова деца су на позицијама од $ди + 1$ до $ди + д$ . Према облику хипа: у мин-хипу сваки елемент има (вредност) приоритет која је веца или једнака од (вредности) приоритета његових родитеља; у маx-хипу сваки елемент има приоритет веци него његови родитељи.^[2]^[3]

Елемент минималног приоритета у мин-хипу (или елемрнт максималног приоритета у маx-хипу) увек се налази на 0 позицији у низу. Да би избрисали овај елемент, последњи елемент x у низу се помера на место 0-тог елемента, а дузина низа се смањује за један. Затим се, све док не испуни услове хипа, елемент x замењује са неким његовим потомком (оним са најмањим приоритетом у мин-хипу или оним са највећим приоритетом у маx-хипу), спуштајуци се низ стабло и позиције у низу. Иста та смена низ стабло мозе да се користи и за увећање приоритета елемената у мин-хипу или за смањење приоритета елемената у маx-хипу.^[2]^[3]

Да би се додао нови елемент у хип, он се убацује на крај низа, а затим се пење смењујући се са својим родитељима све док облик хипа не буде задовољен. Ова иста смена уз стабло може бити корисћена и за смањење приоритета елемената у мин-хипу или увећање приоритета у маx-хипу.^[2]^[3]

Да би се креирао нови хип од низа н елемената, треба кренути обрнутим редослдом, од елемента на н-1 позицији па све до 0 елемента, примењујући смену низ стабло за сваки елемент.^[2]^[3]

Анализа[уреди | уреди извор]

У $д$ -хипу са $н$ елемената и смена низ стабло и смена уз стабло се могу извршити највише $лог д н = лог н / лог д$ . У процесу смене уз стабло свака смена укључује једно поређење елемента са својим родитељем, и то се ради у константном времену. Због тога, време потребно: за додавање новог елемента у хип, да се смањи приоритет неког елемента у мин-хипу, или да се повеца приоритет у маx-хипу је $О(лог н / лог д)$ .У процесу смене низ стабло, свака смена укључује д поређења и потребно је $О(д)$ времена: Потребно је $д - 1$ поређење да се одреди минимум или маxимум деце неког чвора, а затим се тај чвор пореди са родитељем и утврђује се да ли је потребна смена та два чвора. Због тога, време потребно да се избрише корен, или да се увецеа приоритет неког елемента у мин-хипу, или да се смањи приоритет елемента у маx-хипу је $О(д лог н / лог д)$ .^[2]^[3]

Прилоком креирања $д$ -хипа од н елемената , већина тих елемената је на позицији на којој ће се временом наци листови д-стабла, па није потребно вршити смену низ стабло за те елементе. Највише $н / д + 1$ елемената нису листови, и могу се процесом смене низ стабло сменити само једном, и то за $О(д)$ времена које је потребно да се нађе дете које би се заменило са тим чвором. Највише $н / д 2 + 1$ чворова може бити смењемо, процесом смене низ стабло, 2 пута, заузимајући додатних $О(д)$ времена потребног да се изврши још једна смена, итд. Дакле, најавеће потребно време да се хип креира на овај начина је :

\sum _{i=1}^{\log _{d}n}\left({\frac {n}{d^{i}}}+1\right)O(d)=O(n).

^[2]^[3]

Тацна вредност ове суме је еквикалентана следећем:

{\frac {d}{d-1}}(n-s_{d}(n))-(d-1-(n\mod d))(e_{d}(\lfloor {\frac {n}{d}}\rfloor )+1)

,^[9]

с_д(н) је сума свих бројева стандардне основе д репрезентације н и е_д(н) еxпонент од д у фактоеизацији од н.

Ово се редукује у:

2n-2s_{2}(n)-e_{2}(n)

, ^[9]

за д=2 и у

{\frac {3}{2}}(n-s_{3}(n))-2e_{3}(n)-e_{3}(n-1)

,^[9]

за д=3.

Простор потербан за $д -хип$ , са инсерт и делете-мин операцијама је линеран, пошто не користи никакв додатни простор поред низа који садржи листу елемената у хипу.^[2]^[8] Ако желимо да измене приоритета постојецих елемената буду подржане, онда елементи морају да садрже и показиваче на позиције у хипу, који такође користе линеаран простор. ^[2]

Апликације[уреди | уреди извор]

Дајкстра алгоритам за налажење најкраћег пута у графу и Примов алгоритам за минимално разапињуће стабло користе мин-хип у ком је $н$ операција брисања минимума и $м$ операција за смањење приоритета, где је $н$ број врхова у графу а м број ивица. Коришћењем $д$ -хипа са $д = м / н$ , потребно време за ова два типа операција се може смањити до $О(м лог м / н н)$ што је побољшање у односу на $О(м лог н)$ , што је време извршавања у бинарном хипу када је број ивица већи од броја врхова.^[1]^[5] Алтернативана структура је Фибоначи хип, који теориски даје још боље време извршавања $О(м + н лог н)$ , али у пракси $д$ -хип је најмање исто толико брз, а често и бржи од Фибоначи хипа за ове апликације.^[10]

4-хип може да пружи боље перформансе у пракси од бинарног хипа, чак и за операције брисања минимиума.^[2]^[3] Додатно, {{матх|д}-хип се изврсава много брзе него Бинарни хип за велицине хипа која прекорацују велицину кес меморије:

Бинатни хип захтева више промашај кеша и висе погрешних страна виртуалне меморије од $д$ -хипа^[6]^[7]

Референце[уреди | уреди извор]

^ ^а ^б ^в ^г Јохнсон, D. Б. (1975), „Приоритy qуеуес wитх упдате анд финдинг минимум спаннинг треес”, Информатион Процессинг Леттерс, 4 (3): 53—57, дои:10.1016/0020-0190(75)90001-0
^ ^а ^б ^в ^г ^д ^ђ ^е ^ж ^з ^и ^ј ^к Тарјан, Р. Е. (1983), „3.2. д-хеапс”, Дата Струцтурес анд Нетwорк Алгоритхмс, ЦБМС-НСФ Регионал Цонференце Сериес ин Апплиед Матхематицс, 44, Социетy фор Индустриал анд Апплиед Матхематицс, стр. 34—38
^ ^а ^б ^в ^г ^д ^ђ ^е ^ж Wеисс, M. А. (2007), „д-хеапс”, Дата Струцтурес анд Алгоритхм Аналyсис (2нд изд.), Аддисон-Wеслеy, стр. 216, ИСБН 978-0-321-37013-6
^ Јенсен, C.; Катајаинен, Ј.; Витале, Ф. (2004), Ан еxтендед трутх абоут хеапс (ПДФ), Архивирано из оригинала (ПДФ) 09. 06. 2007. г., Приступљено 17. 04. 2014
^ ^а ^б Тарјан 1983. стр. 77 анд 91.
^ ^а ^б Наор, D.; Мартел, C. У.; Матлофф, Н. С. (1991), „Перформанце оф приоритy qуеуе струцтурес ин а виртуал меморy енвиронмент”, Цомпутер Јоурнал, 34 (5): 428—437, дои:10.1093/цомјнл/34.5.428
^ ^а ^б Камп, Поул-Хеннинг (2010), „Yоу'ре доинг ит wронг”, АЦМ Qуеуе, 8 (6)
^ ^а ^б Мортенсен, C. W.; Петтие, С. (2005), „Тхе цомплеxитy оф имплицит анд спаце еффициент приоритy qуеуес”, Алгоритхмс анд Дата Струцтурес: 9тх Интернатионал Wорксхоп, WАДС 2005, Wатерлоо, Цанада, Аугуст 15-17, 2005, Процеедингс, Лецтуре Нотес ин Цомпутер Сциенце, 3608, Спрингер-Верлаг, ИСБН 978-3-540-28101-6, дои:10.1007/11534273_6
^ ^а ^б ^в Суцхенек, Марек А. (2012), „Елементарy Yет Прецисе Wорст-Цасе Аналyсис оф Флоyд'с Хеап-Цонструцтион Програм”, Фундамента Информатицае, ИОС Пресс, 120 (1): 75—92, дои:10.3233/ФИ-2012-751
^ Цхеркасскy, Б. V.; Голдберг, А. V.; Радзик, Т. (1996), „Схортест патхс алгоритхмс: Тхеорy анд еxпериментал евалуатион”, Матхематицал Программинг, 73 (2): 129—174, дои:10.1007/БФ02592101

Спољашње везе[уреди | уреди извор]

[j75-1] а ^б ^в ^г Јохнсон, D. Б. (1975), „Приоритy qуеуес wитх упдате анд финдинг минимум спаннинг треес”, Информатион Процессинг Леттерс, 4 (3): 53—57, дои:10.1016/0020-0190(75)90001-0

[t83-2] а ^б ^в ^г ^д ^ђ ^е ^ж ^з ^и ^ј ^к Тарјан, Р. Е. (1983), „3.2. д-хеапс”, Дата Струцтурес анд Нетwорк Алгоритхмс, ЦБМС-НСФ Регионал Цонференце Сериес ин Апплиед Матхематицс, 44, Социетy фор Индустриал анд Апплиед Матхематицс, стр. 34—38

[w07-3] а ^б ^в ^г ^д ^ђ ^е ^ж Wеисс, M. А. (2007), „д-хеапс”, Дата Струцтурес анд Алгоритхм Аналyсис (2нд изд.), Аддисон-Wеслеy, стр. 216, ИСБН 978-0-321-37013-6

[4] Јенсен, C.; Катајаинен, Ј.; Витале, Ф. (2004), Ан еxтендед трутх абоут хеапс (ПДФ), Архивирано из оригинала (ПДФ) 09. 06. 2007. г., Приступљено 17. 04. 2014

[t2-5] а ^б Тарјан 1983. стр. 77 анд 91.

[nmm91-6] а ^б Наор, D.; Мартел, C. У.; Матлофф, Н. С. (1991), „Перформанце оф приоритy qуеуе струцтурес ин а виртуал меморy енвиронмент”, Цомпутер Јоурнал, 34 (5): 428—437, дои:10.1093/цомјнл/34.5.428

[k10-7] а ^б Камп, Поул-Хеннинг (2010), „Yоу'ре доинг ит wронг”, АЦМ Qуеуе, 8 (6)

[mp05-8] а ^б Мортенсен, C. W.; Петтие, С. (2005), „Тхе цомплеxитy оф имплицит анд спаце еффициент приоритy qуеуес”, Алгоритхмс анд Дата Струцтурес: 9тх Интернатионал Wорксхоп, WАДС 2005, Wатерлоо, Цанада, Аугуст 15-17, 2005, Процеедингс, Лецтуре Нотес ин Цомпутер Сциенце, 3608, Спрингер-Верлаг, ИСБН 978-3-540-28101-6, дои:10.1007/11534273_6

[Suchenek-9] а ^б ^в Суцхенек, Марек А. (2012), „Елементарy Yет Прецисе Wорст-Цасе Аналyсис оф Флоyд'с Хеап-Цонструцтион Програм”, Фундамента Информатицае, ИОС Пресс, 120 (1): 75—92, дои:10.3233/ФИ-2012-751

[10] Цхеркасскy, Б. V.; Голдберг, А. V.; Радзик, Т. (1996), „Схортест патхс алгоритхмс: Тхеорy анд еxпериментал евалуатион”, Матхематицал Программинг, 73 (2): 129—174, дои:10.1007/БФ02592101

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]