Soft hip

U računarstvu, soft hip je varijanta reda sa prioritetom (hip strukture podataka). Ova struktura podataka podržava uobičajene operacije: Kreiraj, Umetni, Spoji, Ukloni i NadjiNajmanji. Njegova prednost je bolja vremenska složenost osnovnih operacija od logaritamske složenosti koju imaju u osnovnoj implementaciji hipa. To se postiže veštackim povećanjem vrednosti određenih ključeva hipa. Dat je bilo koji skup od n operacija, soft hip sa odstupanjem ε (za 0<ε<=1/2) osigurava da, u bilo koje vreme, za svako ε*n, vrednost klučeva se povećava. Smanjenje složenosti za sve operacije je konstantno, osim za operaciju umetni, za koju je potrebno O (log(1/n)) vremena. Soft hip je optimalan za bilo koju vrednost ε u poređenju sa osnovnim hipom. Ova struktura podataka je zasnovana na pokazivaču. Nisu upotrebljeni nikakvi nizovi niti su upotrebljene numeričke pretpostavke na ovim ključevima. Osnovna ideja iza soft hipa je da se elementi pomeraju po strukturi podataka ne pojedinčno kao što je uobičajeno,već u grupama, tako da jedan utiče na ostale. Kao rezultat ovoga ključevi moraju biti povećani kako bi se sačuvalo svojstvo hipa u strukturi podataka. Soft hip može da se koristi za izračunavanje tačne ili približne medijane i optimalne percentile (percentil je mera korisnosti u statistici). Takođe je koristan za približno sortiranje kao i pronalaženje minimalnog razapinjućeg stabla opštih grafova.

Operacije

Spisak operacija

Mi ćemo napraviti jednostavnu varijantu reda sa prioriterom i nazvaćemo ga soft hip. Ova struktura podataka čuva elemente sa ključevima iz potpuno uređenog skupa i podržava sledeće operacije:

• create(S): - operacija kreiraj kreira prazan hip S
• insert(S, x): -operacija umetni umeće element x u hip S
• meld(S, S' ): -operacija spoji formira novi hip sa sadržajem hipa S i S' i ukloni ih nakon toga
• delete(S, x): -operacija ukloni(obriši) uklanja element x iz hipa S
• findmin(S): -operacija nadji najmanji pronalazi element sa najmanjim ključem

Princip funkcionisanja Soft hipa

Soft hip može, u bilo kom trenutku, da poveća vrednost određenih ključeva. Takvi ključevi, sa uvećanim vrednostima, elementi koji ih sadrže nazivaju se ,,pokvareni". Pokvarenost je u potpunosti odvojena od strukture podataka i zato korisnik nema kontrolu nad njim. Naravno, operacija NadjiNajmanji (findmin) vraća element sa minimalnom vrednošću ključa, koji bi mogao ili ne, biti pokvaren. Prednost je brzina, tokom popravke hipa elementi putuju zajedno u paketima u obliku ,,šlepovanja" kako bi uštedeli vreme. Sa informaciono-teorijskog stanovista, kvarenje je način da se smanji entropija podataka uskladištenih u strukturi podataka i olakša popravljanje. Entropija je definisana kao logaritam za osnovu dva, broja različitih ,,posebnih ključnih zadataka". Da bi se videla bitnost ove ideje treba je maksimalno iskoristiti i posmatrati da ako se svaki ključ pokvari tako sto se negova vrednost postavi na beskonačno onda grupa ključeva ima entropiju nula i možemo trivijalno da izvršimo sve operacije u konstantnom vremenu. Zanimljivo je da soft hip pokazuje da entropiju ne treba spustiti na nulu da bi složenost postala konstantna.

Teorema: Počnimo bez početnih podataka, razmotrimo mešavinu sekvence operacija n umetanja. Za bilo koje ε gde je 0<ε<=1/2, soft hip sa odstupanjem ε obezbeđuje da će se svaka operacija izvršiti u konstantnom vremenu, osim za operaciju umetanja, koja zahteva O(log(1/n)) vremena. Ova struktura podataka nikada ne sadrži više od ε*n ,,pokvarenih elemenata" za bilo koje vreme. U poređenju sa osnovnim modelom ove granice su optimalne.

Napomena: Imajte na umu da to ne znači da su samo ε*n elementi ,,pokvareni" u širem skupu operacija. Zahvaljujući brisanjima mnogo više elemenata se može pokvariti. Zapravo, nije teško zamisliti situacju gde su svi elementi pokvareni. Primer: ubacivanje n elemenata i da se onda neprekidno brišu oni koji su ,,pokvareni". Uprkos toj očiglednoj slabosti, soft hip je optimalan i možda čak i iznenađujuće koristan.

Primene

Iznenađujuće, uprkos svojim ograničenjima i svojoj nepredvidivoj prirodi (eng.Nondeterministic algorithm ), Soft hip je koristan prilikom konstrukcije algoritama sa determinističkim ponašanjem(eng.Deterministic algorithm). Ovaj algoritam se koristi za postizanje najbolje složenosti prilikom pronalaženja minimalnog razapinjućeg stabla. Mogu se takođe koristiti za lako pravnljenje selekcionih algoritama kao i algoritama za približno sortiranje (eng.near-sorting algorithms), a to su algoritmi koji postavljaju svaki element u blizini njegovog konačnog položaja, a to je situacija u kojoj je algoritam sortiranja umetanjem brz. Jedan od najjednostavnijih primera je sortiranje izborom. Recimo da želimo da nađemo k-ti najveći element u grupi od n brojeva. Mi ćemo prvo odabrati stepen greške od 1/3, što znači da će najviše 33% ključeva elemenata koje unesemo biti pokvareno. Sada unesemo svih n elemenata u hip - zvaćemo originalne vrednosti "ispravnim ključevima", a vrednosti uskladištene u hip "uskladištenim ključevima". U ovom trenutku najviše n/3 ključeva je pokvareno tj. najviše n/3 uskladištenih elemenata ima ključ veći od ispravnog, a kod svih ostalih elemenata je uneseni ključ jednak ispravnom ključu. Dalje, uklonimo minimalni element iz hipa n/3 puta (ovo se radi u skladu sa uskladištenim elementima). Kako je ukupan broj unosa do sada n, još uvek postoji najviše n/3 pokvarenih ključeva u hipu. Shodno tome, najmanje 2n/3 - n/3 = n/3 od ključeva preostalih u hipu nije pokvareno. Neka L bude element sa najvećim ispravnim ključem među elementima koje smo uklonili. Ključ u elementu L je verovatno veći od njegovog ispravnog ključa (ako je L bio pokvaren), pa čak je i takva uvećana vrednost manja od unesenih ključeva elemenata koji su preostali u hipu (jer smo uklanjali elemente sa minimalnim ključem). Dakle, ispravan ključ L je manji od preostalih n/3 elemenata koji nisu pokvareni u Soft hipu. Tako, L deli elemente negde između 33%/66% i 66%/33%. Zatim ćemo podeliti skup korišćenjem algoritma particionisanja od QUICKSORT i primeniti isti algoritam ponovo na skup elemenata manjih ili skup elemenata većih od L, od kojih nijedan ne može preći 2n/3 elemenata. Posto svako umetanje i brisanje zahteva O(1) vremena, ukupno determinističko vreme je T(n)=T(2n/3)+O(n). Koristeći slučaj 3 u master teoremi (sa epsilon=1 i c=2/3) mi znamo da je T(n)=O(n). Konačan algoritam izgleda ovako:

Pseudo kod algoritma

 function softHeapSelect(a[1..n], k)
     if k = 1 then return minimum(a[1..n])
     create(S)
     for i from 1 to n
         insert(S, a[i])
     for i from 1 to n/3
         x := findmin(S)
         delete(S, x)
     xIndex := partition(a, x)  // Returns new index of pivot x
     if k < xIndex
         softHeapSelect(a[1..xIndex-1], k)
     else
         softHeapSelect(a[xIndex..n], k-xIndex+1)

Reference

• Chazelle, B. „The soft heap: an approximate priority queue with optimal error rate.”. 2000. CiteSeerX 10.1.1.5.9705 .  J. ACM 47, 6 (Nov. 2000), 1012-1027.
• Kaplan, H. and Zwick, U. 2009. A simpler implementation and analysis of Chazelle's soft heaps. In Proceedings of the Nineteenth Annual ACM -SIAM Symposium on Discrete Algorithms (New York, New York, January 4––6, 2009). Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics, Philadelphia, PA, 477-485.