Binäärinen kasa

Binäärikasa , pyramidi [1] tai lajittelupuu on binääripuu, joka täyttää kolme ehtoa:

Arvo missä tahansa kärjessä ei ole pienempi kuin sen jälkeläisten arvot [K 1] .
Kaikkien lehtien syvyys (etäisyys juureen) eroaa enintään 1 kerroksella.
Viimeinen kerros täytetään vasemmalta oikealle ilman "reikiä".

On myös kasoja, joissa arvo missään kärjessä ei päinvastoin ole suurempi kuin sen jälkeläisten arvot. Tällaisia kasoja kutsutaan min-keiksi, ja yllä kuvattuja kasoja max-kekoiksi. Seuraavassa huomioidaan vain max-heap. Kaikki min-keon toiminnot suoritetaan samalla tavalla.

Kätevä tietorakenne lajittelupuulle on taulukko A , jonka ensimmäinen elementti A [1] on juuren elementti ja elementin A [ i ] lapset ovat A [2 i ] ja A [2 i +1 ] (kun numeroidaan elementtejä ensin). Numeroitaessa alkioita nollasta, juurialkio on A [0] ja alkion A [ i ] lapset ovat A [2 i +1] ja A [2 i +2]. Tällä säilytysmenetelmällä ehdot 2 ja 3 täyttyvät automaattisesti.

Kasan korkeus määritellään binääripuun korkeudeksi. Eli se on yhtä suuri kuin reunojen lukumäärä pisimmässä yksinkertaisessa polussa, joka yhdistää kasan juuren yhteen sen lehdistä. Kasan korkeus on , jossa N on puun solmujen lukumäärä. $\Theta \left(\log {N}\right)$

Toiminnallisuus

Voit suorittaa kasalle seuraavat toiminnot:

Lisää elementti kasaan. Monimutkaisuus $O(\log{n})$
Poista maksimielementti kasasta. Työtunnit $O(\log{n})$
Muuta minkä tahansa elementin arvoa. Työtunnit $O(\log{n})$

Näiden toimintojen perusteella voit suorittaa seuraavat toiminnot:

Muuta järjestämätön elementtijoukko kasaksi. Monimutkaisuus $Päällä)$
Lajittele taulukko muuttamalla se kasoksi ja kasa lajitelluksi taulukoksi. Työtunnit $O(n\log{n})$

Tässä on kasaelementtien lukumäärä. Tilan monimutkaisuus - kaikille edellä mainituille toiminnoille ja toiminnoille. $n$ $O(1)$

Näiden toimien yksityiskohtainen kuvaus ja algoritmit sekä niiden suorittamiseen tarvittava Heapify-menettely esitetään seuraavassa osiossa.

Perusmenettelyt

Tässä osiossa esitellään kasan kanssa työskentelyn perustoimenpiteet.

Kasan ominaisuuksien palauttaminen

Jos jokin keon elementeistä muuttuu, se ei välttämättä enää täytä tilausominaisuutta. Palauta tämä ominaisuus käyttämällä Heapify-menettelyä. Se palauttaa kasan ominaisuuden puussa, jonka vasen ja oikea alipuu tyydyttävät sen. Tämä menettely ottaa syötteenä joukon elementtejä A ja indeksiä i . Se palauttaa järjestysominaisuuden koko alipuussa, jonka juuri on elementti A [ i ].

Jos i . elementti on suurempi kuin sen lapsia, koko alipuu on jo kasa, eikä mitään tarvitse tehdä. Muuten vaihdamme i :nnen elementin suurimman lapsista, minkä jälkeen suoritamme Heapifyn tälle pojalle.

Toimenpide valmistuu ajoissa . $O\left(\log {n}\right)$

Keon muodostaminen( A , i ) vasen ← 2 i oikea ← 2 i +1 keon_koko - kasan alkioiden lukumäärä suurin ← i jos vasen ≤ A . kasan_koko ja A [ vasen ] > A [ suurin ] sitten suurin ← vasen jos oikea ≤ A. pinon_koko ja A [ oikea ] > A [ suurin ] sitten suurin ← oikea jos suurin ≠ i sitten Vaihda A [ i ] ↔ A [ suurin ] Kasata ( A , suurin )

Kielillä, jotka eivät tue automaattista tail-rekursion optimointia , toteutuksen tehokkuutta voidaan parantaa poistamalla rekursio.

Kasan rakentaminen

Tämä menettely on suunniteltu luomaan kasa järjestämättömästä syötetietojen joukosta.

Huomaa, että jos suoritat Heapify-toiminnon kaikille taulukon A elementeille viimeisestä ensimmäiseen, siitä tulee kasa. Itse asiassa on helppo todistaa induktiolla, että siihen mennessä, kun Heapify(A, i) suoritetaan, kaikki alipuut, joiden juurten indeksi on suurempi kuin i, ovat kasoja, ja siksi sen jälkeen, kun Heapify(A, i) on suoritettu, kaikki alipuut, joiden juurten indeksi on vähintään i.

Myös Heapify(A,i) ei tee mitään, jos i>N/2 (numeroitaessa ensimmäisestä alkiosta), missä N on taulukon elementtien lukumäärä. Tällaisilla elementeillä ei todellakaan ole lapsia, joten vastaavat alipuut ovat jo kasoja, koska ne sisältävät vain yhden elementin.

Siten riittää kutsua Heapify kaikille taulukon A elementeille alkaen (numeroitaessa ensimmäisestä elementistä) -th:sta ja päättyen ensimmäiseen. $[N/2]$

Build_Heap( A ) A . pinon_koko ← A . pituus i ← ⌊ A . pituus /2⌋ alas 1 do Heapify ( A , i )

Vaikka tässä on n/2 kutsua Heapify-funktiolle monimutkaisesti , voidaan osoittaa, että ajoaika on [1] . $O\left(\log {n}\right)$ $Päällä)$

Keon lajittelu

Heapsort-menettely lajittelee taulukon ilman lisämuistia ajassa . $O\left(n\log {n}\right)$

Ymmärtääksemme sen toiminnan voimme kuvitella, että olemme vaihtaneet ensimmäisen elementin (eli juuren) viimeiseen. Sitten viimeinen elementti on suurin. Jos sen jälkeen jätetään viimeinen elementti pois kasosta (eli pienennetään sen pituutta muodollisesti yhdellä), ensimmäiset N-1 elementtiä täyttävät keon ehdot kaikki paitsi ehkä juuri. Jos soitat Heapifylle, ensimmäisistä N-1 elementistä tulee kasa ja viimeisistä on suurempi kuin ne kaikki. Toistamalla nämä vaiheet N-1 kertaa, lajittelemme taulukon.

Kasalajittelu ( A ) Build_Heap( A ) for i ← A . pituus alas 1 do Vaihda A [1] ↔ A [ i ] A . pinon_koko ← A . pinon_koko -1 Kasaa kasaan ( A ,1)

Elementin arvon muuttaminen

Heap_Increase_Key-proseduuri korvaa kasan elementin uudella avaimella, jonka arvo on suurempi tai yhtä suuri kuin alkuperäisen elementin arvo . Tyypillisesti tätä menettelyä käytetään mielivaltaisen elementin lisäämiseen kasaan. Aika monimutkaisuus . $O\left(\log {n}\right)$

Jos elementti on pienempi kuin sen emoelementti, ehto 1 täyttyy koko puulle, eikä mitään muuta tarvitse tehdä. Jos hän on isompi, vaihdamme paikkaa isänsä kanssa. Jos sen jälkeen isä on isoisää isompi, vaihdamme isän isoisään ja niin edelleen. Toisin sanoen liian suuri elementti kelluu huipulle.

Heap_Increase_Key( A , i , avain ) jos avain < A [ i ] sitten virhe "Uusi avain on pienempi kuin edellinen" A [ i ] ← näppäin , kun taas i > 1 ja A [⌊ i /2⌋] < A [ i ] vaihda A [ i ] ↔ A [⌊ i / 2⌋ ] i ← ⌊ i /2⌋

Jos elementin arvoa on tarpeen pienentää, voit soittaa Heapifylle.

Elementin lisääminen

Suorittaa elementin lisäämisen kasaan ajoissa . $O\left(\log {n}\right)$

Satunnaisen elementin lisääminen keon loppuun ja tilausominaisuuden palauttaminen Heap_Increase_Keyllä.

Heap_Insert( A , avain ) A . pinon_koko ← A . pinon_koko +1 A [ A . heap_size ] ← -∞ Heap_Increase_Key( A , A . kasan_koko , avain)

Maksimielementin purkaminen

Hakee maksimielementin kasasta ajallaan . $O\left(\log {n}\right)$

Poisto suoritetaan neljässä vaiheessa:

juurielementin arvo (se on maksimi) tallennetaan myöhempää palautusta varten
viimeinen elementti kopioidaan juureen ja poistetaan sitten kasosta
nimeltä Heapify juurissa
tallennettu elementti palautetaan

Keon_Ote_Max( A ) , jos A . kasan_koko [ A ] < 1 sitten virhe "Keko on tyhjä" max ← A [1] A [1] ← A [ A .heap_size] A . pinon_koko ← A . pinon_koko -1 Heapify( A , 1) paluu max

Katso myös

Linkit

↑ 1 2 Kormen, T. , Leizerson, C. , Rivest, R. , Stein, K. Luku 6. Heapsort // Algoritmit: rakentaminen ja analyysi = Introduction to Algorithms / Ed. I. V. Krasikova. - 2. painos - M. : Williams, 2005. - S. 178 - 193. - ISBN 5-8459-0857-4 .

Kommentit

↑ Jos lajittelujärjestys on päinvastainen, minkään solmun arvo ei saa olla suurempi kuin sen jälkeläisten arvot.

Tietorakenteet
Luettelot	joukko yksittäin linkitetty lista kaksoislinkitetty lista Passilista
puut	B-puu Binäärihakupuu AVL puu Puna-musta puu pino
Laskee	Suunnattu graafi Suunnattu asyklinen graafi Binääripäätöskaavio Hypergraph
muu	Hash-taulukko Pino

Puu (tietorakenne)
Binäärihakupuu Puu (graafiteoria) puun rakenne
Binääripuut	binäärinen puu T-puu
Itsetasapainottavat binaaripuut	AA puu AVL puu Puna-musta puu Splay-puu puu sakkoilla karteesinen puu Fibonacci puu B-puu T-puu
B-puut	2-3-puu B⁺-puu B*-puu B x -puu UB puu 2-3-4 puu (a,b)-puu tanssiva puu
etuliite puita	suffiksi puu Pakattu etuliitepuu Kolmiosainen hakupuu
Avaruuden binaarinen osiointi	k-ulotteinen puu VP-puu
Ei-binääripuut	Quadtree oktreen Harva Voxel Octree eksponentiaalinen puu PQ puu
Avaruuden hajottaminen	R-puu Hilbert R-puu R+-puu R*-puu X-puu M-puu Fenwick puu Segmenttipuu
Muut puut	pino hash puu sormipuu metrinen puu Päällystyspuu BK-puu Kaksiketjuinen puu iDistance Linkistä leikattu puu LSM puu
Algoritmit	Leveys ensimmäinen haku Ensimmäinen syvyyshaku DSW-algoritmi kattava puu protokolla