Kasa (tietorakenne)

Tietojenkäsittelytieteessä kasa on puutyyppinen erikoistietorakenne , joka täyttää keon ominaisuuden : jos B on solmun A lapsisolmu , niin avain( A ) ≥ avain( B ). Tästä seuraa, että suurimman avaimen omaava elementti on aina keon juurisolmu, joten joskus tällaisia ​​kasoja kutsutaan max-kekoiksi (vaihtoehtoisesti, jos vertailu käännetään, pienin elementti on aina juurisolmu, tällaisia ​​kasoja kutsutaan ns. min-kasat ). Ei ole rajoituksia, kuinka monta lapsisolmua kullakin pinosolmulla on, vaikka käytännössä tämä määrä on yleensä enintään kaksi. Keko on prioriteettijonoksi kutsutun abstraktin tietotyypin tehokkain toteutus . Kasat ovat tärkeitä joissakin tehokkaissa graafialgoritmeissa , kuten Dijkstran algoritmissa d- kekoille ja heapsortille .  

Keon tietorakennetta ei pidä sekoittaa dynaamisen muistin allokoinnin keon käsitteeseen . Termiä käytettiin ensin erityisesti tietorakenteille. Jotkut varhaiset suositut ohjelmointikielet, kuten LISP , tarjosivat dynaamista muistin varausta käyttämällä "kasa"-tietorakennetta, joka antoi nimensä varatulle muistimäärälle. [1] .

Kekot toteutetaan yleensä taulukoina, mikä eliminoi osoittimien tarpeen elementtien välillä.

Seuraavat toiminnot suoritetaan yleensä kasoilla:

• etsi maksimi tai etsi minimi : etsi maksimielementti max-keosta tai minimielementti min-keosta, vastaavasti
• poista max tai poista min : poista juurisolmu max- tai min-keosta, vastaavasti
• lisäysavain tai vähennysavain : päivitä avain max- tai min-keossa, vastaavasti
• add : Lisää uusi avain kasaan.
• yhdistä : kahden kasan yhdistäminen uuden kasan luomiseksi, joka sisältää molempien alkuperäisten elementit.

Vaihtoehdot

• 2-3 kasaa
• biparent kasa
• binäärinen kasa
• binomiaalinen kasa
• Brodalin jono
• Kasa D-lasten kanssa
• fibonacci-kasa
• Kasa vasemmanpuoleisin prioriteetti
• Kaksoispino
• epäsymmetrinen kasa
• pehmeä kasa
• Kolmiosainen kasa
• karteesinen puu

Varianttien teoreettisten arvioiden vertailu

Alla on arvioita tietyntyyppisten kasojen toimintojen laskutoimitusten aikamonimutkaisuudesta. [1] Kun arvo on merkitty tähdellä, arvio perustuu kuoletusanalyysiin (huonoin aika), muuten arvio on tavallinen huonoin tapaus. O(F) antaa asymptoottisen ylärajan ja Θ(F) on asymptoottisesti tarkka estimaatti (katso merkintä "O" suuri ja "o" pieni ). Toimintojen nimet valitaan min-kekolle.

(*) Kuoletusaika
(**) Missä n on suurimman kasan koko

Huomaa, että "Brodalin jono" on toteutus rinnakkaisesta prioriteettijonosta, jonka on kehittänyt Gert Brodalin johtama ryhmä. [3]

Sovellus

Keon tietorakenteilla on monia käyttötarkoituksia.

• Heapsort : Yksi parhaista käytössä olevista lajittelumenetelmistä, jossa ei ole neliöllistä pahimman tapauksen skenaarioita.
• Hakualgoritmit: Kasaa käytettäessä minimin, maksimin, molempien, mediaanin tai k :nneksi suurimman elementin etsiminen voidaan tehdä lineaarisessa ajassa (usein jopa vakioajassa). [neljä]
• Graafialgoritmit : Keon käyttäminen tietorakenteena sisäiseen läpikulkuun johtaa suoritusajan lyhenemiseen polynomijärjestyksessä. Esimerkkejä tällaisista ongelmista ovat Primin minimivirittävän puun rakennusalgoritmi ja Dijkstran lyhimmän polun ongelma .

Täydellinen ja lähes täydellinen binäärikeko voidaan esittää erittäin tehokkaasti käyttämällä indeksitaulukkoa . Ensimmäinen (tai viimeinen) elementti sisältää juuren. Matriisin kaksi seuraavaa elementtiä sisältävät juuren lapsisolmut. Seuraavat neljä elementtiä sisältävät neljä lasta kahdesta solmusta, jotka ovat juuren lapsia jne. Siten tasosolmun lapset nsijoittuvat yhdestä indeksoidulle taulukolle paikoille ja joukolle tai sijoille 2nja taulukolle indeksoidulle taulukolle. nollasta. Tämän avulla voit siirtyä ylös tai alas puussa tekemällä yksinkertaisia ​​taulukkoindeksilaskelmia. Kasan tasapainotus tehdään järjestämällä uudelleen epäkunnossa olevia elementtejä. Koska voimme rakentaa kasan käyttämällä taulukkoa, jossa ei ole ylimääräistä muistia (esimerkiksi solmuille), voimme käyttää kasalajittelua taulukon järjestämiseen paikoilleen. 2n+12n+12n+2

Toteutukset

• C++ -standardimallikirjasto tarjoaa funktiomalleja keonhallintaan make_heap, push_heap ja pop_heap (binäärikeko on yleensä toteutettu), jotka toimivat hajasaantiiteraattoreilla . Menetelmät käyttävät iteraattoreita taulukkoviittauksina ja suorittavat taulukosta kekoon -muunnoksen.
• Java 2 Platform Java Pattern Set (versiosta 1.5 alkaen) tarjoaa binäärikeon toteutuksen java.util.PriorityQueue<E>-luokassa.
• Pythonissa on heapq-moduuli, joka toteuttaa prioriteettijonoja binäärikeon avulla. [5]
• PHP :n versiosta 5.3 lähtien menetelmät maxheap (SplMaxHeap) ja minheap (SplMinHeap) ovat saatavilla vakiokirjastossa.
• Perlillä on toteutuksia binääri-, binomi- ja fibonacci-kasoista Comprehensive Archive Networkissa . [6]

Katso myös

• Pino
• Lajittelualgoritmi

Muistiinpanot

1. ↑ 1 2 3 Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest (1990): Introduction to algoritms. MIT Press / McGraw-Hill.
2. ↑ Iacono, John (2000), Parannetut ylärajat kasojen yhdistämiselle , Proc. 7th Scandinavian Workshop on Algorithm Theory , voi. 1851, Lecture Notes in Computer Science, Springer-Verlag, s. 63–77 , DOI 10.1007/3-540-44985-X_5 
3. ↑ Parallel Priority Queue with Constant Time Operations , < http://www.ceid.upatras.gr/faculty/zaro/pub/jou/J9-JPDC-pq.pdf > Arkistoitu 26. heinäkuuta 2011 Wayback Machinessa 
4. ↑ Frederickson, Greg N. (1993), Optimal Algorithm for Selection in a Min-Heap , Information and Computation , voi. 104, Academic Press, s. 197–214, doi : 10.1006/inco.1993.1030 , < http://ftp.cs.purdue.edu/research/technical_reports/1991/TR%2091-027.pdf > Arkistoitu 3. joulukuuta 2012 Machine at the Wayback 
5. ↑ Python heapq . Haettu 31. toukokuuta 2011. Arkistoitu alkuperäisestä 18. lokakuuta 2012. (määrätön)
6. ↑ Perl Heap