Yhdistä kasa
Yhdistettävä kasa on tietorakenne , joka tukee seuraavia viittä toimintoa :
- Tyhjän kasan luominen ( eng. Make hep );
- Solmun lisääminen kasaan ( englanti Insert );
- Etsi keosta solmua, jolla on vähimmäisavain ( englanniksi Minimum );
- Minimiavaimella varustetun solmun poistaminen kasasta ( eng. Extract minimum );
- Luodaan uusi kasa , joka sisältää kaikki pinojen solmut ja ( eng. Union ).
Toteutukset
Seuraavat kaksi tietorakennetta ovat yhdistettyjä keon toteutuksia:
Nämä tietorakenteet tukevat myös kahta muuta toimintoa:
- Uuden avainarvon ( Decrease key ) määrittäminen keon solmulle (oletetaan, että uusi avainarvo ei ylitä nykyistä);
- Solmun poistaminen kasasta ( fin. Delete ).
| Operaatio | binomiaalinen kasa | fibonacci-kasa |
|---|---|---|
| tehdä kasa | Θ(1) | Θ(1) |
| Lisää | O ( lgn ) | Θ(1) |
| Minimi | O ( lgn ) | Θ(1) |
| Poisto minimi | Θ(lg n ) | O ( lgn ) |
| liitto | Ω(lg n ) | Θ(1) |
| Pienennä näppäin | Θ(lg n ) | Θ(1) |
| Poistaa | Θ(lg n ) | O ( lgn ) |
Huomautus: Binomial-keon osalta pahimman tapauksen aika, Fibonacci-keon osalta kuoletusaika.
Kommentti. Yhdistetyt kasat ovat oletusarvoisesti ei-väheneviä yhdistettäviä kasoja ( Mergeable min-heap ). On myös ei-nousevia yhdistettäviä kasoja ( Mergeable max-heap ), jotka tukevat seuraavia toimintoja:
- Tyhjän kasan luominen ( eng. Make hep );
- Solmun lisääminen kasaan ( englanti Insert );
- Etsi kasasta solmua, jolla on maksimiavain ( eng. Maximum );
- Maksimiavaimella varustetun solmun poistaminen kasasta ( Pura maksimi );
- Luodaan uusi kasa , joka sisältää kaikki pinojen solmut ja ( eng. Union ).
- Uuden avainarvon määrittäminen keon solmulle ( Suurenna avain );
- Solmun poistaminen kasasta ( fin. Delete ).
Kirjallisuus
- Thomas H. Kormen et al. Algoritmit: rakentaminen ja analyysi. - 2. painos - M . : Williams Publishing House , 2007. - S. 1296. - ISBN 5-8459-0857-4 .