Хип (структура података)
 | Овај чланак је започет или проширен кроз пројекат семинарских радова. Потребно је проверити превод, правопис и вики-синтаксу. Када завршите са провером, допишете да након |проверено=. |
У компјутерским наукама, хрпа је структура података организована по принципу стабла која мора да задовољава услов хрпе: кључ сваког чвора је већи или једнак од кључева њихових синова. Када је максималан број деце једног чвора два, то је бинарна хрпа.
Хрпа је изузетно битан у неким алгоритмима, као што је Дијкстра алгоритам и хеапсорт. Хрпа је веома корисна структура података када треба да се уклони чвор највишег или најнижег приоритета.
Чвор је једна меморијска јединица и садржи кљуц тј, податак. Сваки чвор има свог претка, сем корена стабла који представља врх хијерархије. Ако је чвор А предак цвора Б, онда је Б потомак од А. Чвор без потомака се зове лист, а чвор који није лист се зове унутрашњи чвор. Кључ сваког чвора је увек веци или једнаки од кљуцева његових потамака и највеци кљуц је у корену стабла. Не постоји посебна веза између чворова на истом нивоу или браће. Како је хрпа бинарно стабло,има најмању могућу висину - О(лог н) за хрпа са н чворова. Како између браће не постоји веза и чвор је директно везан само са родитељем и децом (првим претком и потомцима), не постоји могућност за обилазак стабла.
Хрпа је максимално ефикасна имплементација апстрактног типа података који се зове ред са приоритетом. У ствари редове са приоритетом цесто називају "хрпом", без обзира на то како су имплеметирани. Упркос сличности имена "хрпа" са именима "стек" и "ред",друга два су апстрактни тип података, док је хрпа специфична структура података и "ред са приоритетом" је погодан назива са апстрактни тип података.
Операције у хрпи[уреди | уреди извор]
Операције уклањања и уметања елемента се обављају тако да се прво задовољи својство облика додавањем или уклањањем чвора са дна стабла, а затим се сређује својство хрпе кретањем по хрпи. Обе операција захтевају временску сложеност О(лог н), што значи да се ефикасно извршавају.Недостатак хрпе је што се тражење кључа не може извршити тако једноставно. Сматраћемо да су кључеви чворова хрпе смештени у вектор А,док је н број елемената хрпе. Елементи су на индекисама од 1 до н.
Уметање[уреди | уреди извор]
- Број н се увећа за један и нови елемент се упише на слободну позицију А[н]
- Упоређујемо тај кључ и кључ елемента на позицији А[и],где је и=⌊н/2⌋,па ако је већи од њега,мењају им се места
- Поступак се наставља премештањем кључа навише,све док н буде мањи или једнак од оца
- Индуктивна хипотеза: Ако је уметнути кључ након премештања у чвору А[ј], онда је то корен исправне хрпе и ако се то подстабло уклони,остатак стабла задовољава услов хрпе
[уреди | уреди извор]
- кључ највећег елемента је А[1], па га је лако наћи
- заменимо елементе А[н] и А[1]
- н смањимо за један
- x=А[1] а y=маx{А[2], А[3]}(већи од синова корена)
- ако је x ≥ y,онда је комплетно стабло исправна хрпа
- инаце,после замене кључева елемената x и y,,подстабло са непромењеним кореном остаје исправана хрпа,а у другом подстаблу је промењен корен
- рекурзивно се сређује подстабло
- индуктивна хипотеза: ако је после и корака x на позицији А[ј],онда само подстабло са кореном А[ј] евентуално не задовољава услов хрпе. Даље се x упоређује са А[2ј] и А[2ј+1] и даље се замењују места ако треба.
Врсте хрпе[уреди | уреди извор]
- 2-3 хрпа
- Б-хрпа
- Беап
- Бинарна хрпа
- Биномна хрпа
- Бродал ред
- д хрпа
- Фибоначи хрпа
- Лефтист хрпа
- Паиринг хрпа
- Скеw хрпа
- Софт хрпа
- Wеак хрпа
- Леаф хрпа
- Радиx хрпа
- Рандомизед мелдабле хрпа
- Тернарy хрпа
- Треап
Поређење теоретских граница за варијанте[уреди | уреди извор]
О(ф) даје асимтотску горњу границу и Θ(ф) је асимптотски блиска граница(погледати нотацију велико О). Ради се са мин-хрпом.
| Операција | Бинарни хип | Биномни хип | Фибоначи хип | Паиринг хип[1] | Бродал ред [2][3]}} | Ранк-паиринг[4] |
|---|---|---|---|---|---|---|
| наћи мин | Θ(1) | Θ(1) | Θ(1) | Θ(1) | Θ(1) | Θ(1) |
| избриши мин | Θ(лог н) | Θ(лог н) | О(лог н) | О(лог н) | О(лог н) | О(лог н) |
| убаци | Θ(лог н) | О(лог н) | Θ(1) | Θ(1) | Θ(1) | Θ(1) |
| смањи кључ | Θ(лог н) | Θ(лог н) | Θ(1) | О(лог н) | Θ(1) | Θ(1) |
| спајање | Θ(н) | О(лог н) | Θ(1) | Θ(1) | Θ(1) | Θ(1) |
Имплементација хрпе[уреди | уреди извор]
Хрпа се може реализовати експлицитно или имплицитно задатим стаблом.Експлицитно значи да се користи структура података која садржи кључ и показиваче ка синовима(и некада ка оцу).Имплицитно значи да се чворови стављају у низ и да су њихове везе одређене њиховом позицијом у вектору.
Имплементација помоћу низа[уреди | уреди извор]
Свако бинарно стабло може бити сачувано преко низа, али пошто је бинарна хрпа скоро увек комплетно бинарно стабло,имплементација помоћу низа,без показивача је погодна.Позиција корена мозе бити на индеxу 0 или 1.Следећа два елемента ће да садрже његову децу.Следећа четири децу од два чвора који су деца од корена итд. Тако да ће деца чвора на позицији н бити на позицији 2н и 2н+1. Ово омогућава померање елемената користећи прорачуне индеxа.Балансирање хрпе се ради замењивањем елемената који нису на месту.Како можемо да направимо хрпу од низа без коришћења додатне меморије(за чворове нпр),хеапсорт може да буде коришћен за сортирање низова у месту. Ова имплементација се користи код хеапсорт алгоритма за сортирање где је дозвољено да се простор у улазни низ поново искористи за чување хрпе. Алгоритам врши сортирање у месту. Имплементација је такође корисна као и ред са приоритетом где коришћење динамичког низа дозвољава убацивање неограниченог броја чланова.
Примена[уреди | уреди извор]
- Хеапсорт: Један од најбољих метода за сортирање у месту без квадратне сложености за најгоре случајеве.
- Алгоритем избора: Хрпа дозвољава приступ највећем и најмањем елементу у константном времену,а осталим селекцијама (као што су медијана и к-ти елемент) у суб-линеарном времену над подацима који су у хрпи.[5]
- Грефовски алгоритми:Користећи хрпу као интерну структуру података, време извршавања може бити смањено полиномијано. Примари таквих проблема су Примов алгоритам и Дијкстрин алгоритам.
- Ред са приоритетом: Ред са приоритетом је апстрактни концепт као "листа" или "мапа";Као што листа може бити имплеметирана повезаном листом или као низ,ред са приоритетом може бити имплеметиран помоћу хрпе или других метода.
- Статистика реда: Структура података хеап може да се користи за ефикасно проналажење к-тог најмањег (или највећег) елемента у низу.
Референце[уреди | уреди извор]
- ^ Иацоно, Јохн (2000), „Импровед уппер боундс фор паиринг хеапс”, Проц. 7тх Сцандинавиан Wорксхоп он Алгоритхм Тхеорy, Лецтуре Нотес ин Цомпутер Сциенце, 1851, Спрингер-Верлаг, стр. 63—77, дои:10.1007/3-540-44985-X_5
- ^ http://www.cs.au.dk/~gerth/papers/soda96.pdf
- ^ Гоодрицх, Мицхаел Т.; Тамассиа, Роберто (2004). „7.3.6. Боттом-Уп Хеап Цонструцтион”. Дата Струцтурес анд Алгоритхмс ин Јава (3рд изд.). стр. 338—341.
- ^ Хаеуплер, Бернхард; Сен, Сиддхартха; Тарјан, Роберт Е. (2009). „Ранк-паиринг хеапс” (ПДФ). СИАМ Ј. Цомпутинг: 1463—1485. Архивирано из оригинала (ПДФ) 21. 04. 2014. г. Приступљено 20. 04. 2014.
- ^ Фредерицксон, Грег Н. (1993), „Ан Оптимал Алгоритхм фор Селецтион ин а Мин-Хеап”, Информатион анд Цомпутатион (ПДФ), 104 (2), Ацадемиц Пресс, стр. 197—214, дои:10.1006/инцо.1993.1030, Архивирано из оригинала (ПДФ) 03. 12. 2012. г., Приступљено 19. 04. 2014
Спољашње везе[уреди | уреди извор]
- Хеап ат Wолфрам МатхWорлд
- "Алгоритми" Миодраг Живковић