Slučajan promešan hip — разлика између измена
Садржај обрисан Садржај додат
мНема описа измене |
Нема описа измене |
||
Ред 1:
{{Neprovereni seminarski}}
U [[Informatika|informatici]], '''slučajni promešani hip''' (takođe i promešani [[Hip (struktura podataka)|hip]] i slučajan promešan prioritetni [[Red (tip podataka)|red]]) je prioritetni red. Slučajni promešani hip je bazična [[struktura podataka]] u kojoj je osnovna struktura takođe hip-red binarno stablo. Kako god, nema ograničenja u obliku osnovnog binarnog stabla.
Ovaj pristup ima brojna poboljšanja u odnosu na slične strukture podataka. Ova struktura nudi sjajna pojednostavljenja: sve operacije slučajnog promešanog hipa su lake za implementaciju i konstantni faktori u njenoj implementaciju su mali,takođe nema potrebe za čuvanjem uslova balansa.<ref name="Gambin">A. Gambin and A. Malinowski. 1998. Randomized Meldable Priority Queues. In Proceedings of the 25th Conference on Current Trends in Theory and Practice of Informatics: Theory and Practice of Informatics (SOFSEM '98), Branislav Rovan (Ed.). Springer-Verlag, London, UK, UK, 344-349.</ref>
Ред 50:
=== Dodatne operacije ===
Neke dodatne operacije mogu biti implementirane za promešan hip, a da imaju složenost -{''O''(log''n'')}- u najgorem slučaju. Te operacije su:
* -{Brisanje(u)}- - Briše sve čvorove u i njihove ključeve iz hipa.
* -{Apsorbovanje(Q)}- - dodaje sve elemente hipa Q u ovaj hip,takodje prazni Q u procesu
Ред 81:
Promešan hip je prvi put predložen [[1998]]. od strane Gambina i Malinkoskog.<ref name="Gambin" />
== Varijante ==
Slučajan promešan hip je
* [[Binomni hip]]
* [[Fibonači hip]]
| |||