Sisällysluettelo:
Määritelmä - mitä Heap tarkoittaa?
Kasa on tietorakenteen yhteydessä puupohjainen tietorakenne, joka tyydyttää kasan ominaisuuden, jolloin jokaiselle elementille annetaan avainarvo tai painotus. Alemman arvon avaimella on aina ylätaso, jolla on korkeamman arvon avain. Tätä kutsutaan max-kasan rakenteeksi, ja kaikissa solmuissa juurisolmulla on korkein avain.
Joskus puupohjaisella rakenteella on käänteinen rakennesääntö, jossa korkeamman arvon avaimella varustetulla elementillä on aina alhaisempi arvo-avain vanhemman solmuna. Tätä kutsutaan min-kasan rakenteeksi, ja kaikissa solmuissa juurisolmulla on alhaisin avain.
Techopedia selittää Heap
Lasten lukumäärällä, joka jokaisella solmulla voi olla kasassa, ei ole käytännöllisiä rajoituksia, vaikka jokaisella solmulla on yleensä enintään kaksi. Pinoa pidetään abstraktin tietotyypin, joka tunnetaan prioriteettijonona, tehokkaimpana toteutuksena. Kasan toteutus on välttämätöntä erilaisissa kuvaaja-algoritmeissa (mukaan lukien Dijkstra-algoritmi) sekä kasa-lajittelualgoritmissa.
Kasoissa on useita variansseja, jotka toimivat abstraktina tietotyypin prioriteettijonojärjestelmissä erittäin tehokkaasti. Monet sovellukset, kuten kuvaajaalgoritmit, vaativat prioriteettijonojen toteuttamisen.
Taulukko on yleisin kasan toteutusmuoto, jossa ei tarvita osoittimia linkittämään sen elementtejä.
Kaset tekevät useita toimintoja, mukaan lukien:
- Etsi-max: Etsii korkeinta avainsolmua solmuryhmän keskuudessa
- Find-min: Etsii alimpaa avainsolmua solmujen ryhmässä
- Poista-max: Poistaa korkeimman näppäinsolmun joukosta solmuja
- Poista min: Poistaa alimman näppäinsolmun joukosta solmuja
Kasaan sisältyy myös toimintoja, jotka suorittavat yhdistämisen, lisäämisen ja näppäinten muuttamisen.
Tämä määritelmä on kirjoitettu tietorakenteen yhteydessä
