Opas kasoihin Pythonissa

esittely

Kuvittele vilkas lentokenttä, jonka lentoja nousee ja laskeutuu minuutin välein. Aivan kuten lennonjohtajat priorisoivat lennot kiireellisyyden perusteella, kasat auttavat meitä hallitsemaan ja käsittelemään tietoja tiettyjen kriteerien perusteella varmistaen, että "kiireellisimmät" tai "tärkeimmät" tiedot ovat aina käytettävissä ylhäältä.

Tässä oppaassa lähdemme matkalle ymmärtääksemme kasoja alusta alkaen. Aloitamme selvittämällä, mitä kasat ovat ja niiden luontaiset ominaisuudet. Sieltä sukeltamme Pythonin omaan kasojen toteutukseen, the heapq moduuli ja tutustu sen runsaisiin toimintoihin. Joten jos olet koskaan miettinyt, kuinka hallita tehokkaasti dynaamista tietojoukkoa, jossa tarvitaan usein korkeimman (tai alhaisimman) prioriteetin elementtiä, sinulla on hyvä juttu.

Mikä on kasa?

Ensimmäinen asia, jonka haluat ymmärtää ennen sukeltamista kasojen käyttöön, on mikä on kasa. Kasa erottuu tietorakenteiden maailmassa puupohjaisena voimana, joka on erityisen taitava järjestyksen ja hierarkian ylläpitäminen. Vaikka se saattaa muistuttaa binaaripuuta kouluttautumattomalle silmälle, sen rakenteen ja sääntöjen vivahteet erottavat sen selvästi.

Yksi kasan määrittelevistä ominaisuuksista on sen luonne a täydellinen binääripuu. Tämä tarkoittaa, että puun jokainen taso, paitsi ehkä viimeinen, on täysin täytetty. Tällä viimeisellä tasolla solmut täyttyvät vasemmalta oikealle. Tällainen rakenne varmistaa, että kasoja voidaan esittää ja käsitellä tehokkaasti taulukoiden tai listojen avulla, jolloin kunkin elementin sijainti taulukossa peilaa sen paikkaa puussa.

Kasan todellinen olemus piilee kuitenkin siinä tilaus. Jonkin sisällä max kasa, minkä tahansa solmun arvo ylittää tai on yhtä suuri kuin sen aliarvot ja sijoittaa suurimman elementin juuri juureen. Toisaalta a min kasa toimii päinvastaisella periaatteella: minkä tahansa solmun arvo on joko pienempi tai yhtä suuri kuin sen lapsiarvot, mikä varmistaa, että pienin elementti on juurissa.

Edistyessämme sukeltamme syvemmälle siihen, kuinka nämä kasojen luontaiset ominaisuudet mahdollistavat tehokkaan toiminnan ja miten Pythonin heapq moduuli integroi saumattomasti kasoja koodauspyrkimyksiimme.

Kasojen ominaisuudet ja ominaisuudet

Kasat ainutlaatuisella rakenteella ja järjestysperiaatteillaan tuovat esiin joukon erilaisia ​​ominaisuuksia ja ominaisuuksia, jotka tekevät niistä korvaamattomia erilaisissa laskennallisissa skenaarioissa.

Ensinnäkin kasat ovat luonnostaan ​​tehokas. Niiden puupohjainen rakenne, erityisesti täydellinen binääripuumuoto, varmistaa, että toiminnot, kuten prioriteettielementtien (maksimi tai minimi) lisääminen ja poimiminen, voidaan suorittaa logaritmisessa ajassa, tyypillisesti O (log n). Tämä tehokkuus on siunaus algoritmeille ja sovelluksille, jotka vaativat usein pääsyn tärkeisiin elementteihin.

Toinen kasojen merkittävä ominaisuus on niiden muistin tehokkuus. Koska kasat voidaan esittää taulukoiden tai listojen avulla ilman erityisiä osoittimia ala- tai yläsolmuihin, ne säästävät tilaa. Jokaisen elementin sijainti taulukossa vastaa sen paikkaa puussa, mikä mahdollistaa ennakoitavan ja suoraviivaisen läpikäynnin ja manipuloinnin.

Kasojen järjestysominaisuus, olipa se sitten max- tai min-kasa, varmistaa sen juurilla on aina korkeimman prioriteetin elementti. Tämä johdonmukainen järjestys mahdollistaa nopean pääsyn tärkeimpään elementtiin ilman, että koko rakennetta tarvitsee etsiä.

Lisäksi kasat ovat monipuolinen. Vaikka binäärikasat (joissa kummallakin vanhemmalla on enintään kaksi lasta) ovat yleisimpiä, kasat voidaan yleistää siten, että niillä on enemmän kuin kaksi lasta. d-ary kasoja. Tämä joustavuus mahdollistaa hienosäädön erityisten käyttötapausten ja suorituskykyvaatimusten perusteella.

Lopuksi kasat ovat itsesäätyvä. Aina kun elementtejä lisätään tai poistetaan, rakenne järjestää itsensä uudelleen säilyttääkseen ominaisuudet. Tämä dynaaminen tasapainotus varmistaa, että kasa pysyy jatkuvasti optimoituna ydintoimintojaan varten.

Kun perehdymme syvemmälle Pythonin toteutukseen ja käytännön sovelluksiin, kasojen todellinen potentiaali avautuu edessämme.

Kasojen tyypit

Kaikki kasat eivät ole samanarvoisia. Järjestyksen ja rakenteellisten ominaisuuksiensa mukaan kasat voidaan luokitella eri tyyppeihin, joista jokaisella on omat käyttötarkoituksensa ja etunsa. Kaksi pääluokkaa ovat max kasa ja min kasa.

A:n erottuvin piirre max kasa on, että minkä tahansa solmun arvo on suurempi tai yhtä suuri kuin sen lapsien arvot. Tämä varmistaa, että kasan suurin elementti sijaitsee aina juuressa. Tällainen rakenne on erityisen hyödyllinen, kun on tarve käyttää usein maksimielementtiä, kuten tietyissä prioriteettijonototeutuksissa.

Max-keon vastine, a min kasa varmistaa, että minkä tahansa solmun arvo on pienempi tai yhtä suuri kuin sen lapsien arvot. Tämä sijoittaa kasan pienimmän elementin juureen. Vähimmäiskasat ovat korvaamattomia skenaarioissa, joissa pienin elementti on ensiarvoisen tärkeä, kuten algoritmeissa, jotka käsittelevät reaaliaikaista tietojenkäsittelyä.

Näiden ensisijaisten luokkien lisäksi kasat voidaan erottaa myös niiden haarautumistekijän perusteella:

Vaikka binaariset kasat ovat yleisimpiä, ja kummallakin vanhemmalla on enintään kaksi lasta, kasojen käsite voidaan laajentaa solmuihin, joilla on enemmän kuin kaksi lasta. Jonkin sisällä d-ary kasa, jokaisella solmulla on enintään d lapset. Tämä muunnelma voidaan optimoida tiettyjä skenaarioita varten, kuten puun korkeuden pienentäminen tiettyjen toimintojen nopeuttamiseksi.

Binomiaalinen kasa on joukko binomiaalipuita, jotka määritellään rekursiivisesti. Binomiaalisia kasoja käytetään prioriteettijonojen toteutuksissa ja ne tarjoavat tehokkaita yhdistämistoimintoja.

Nimetty kuuluisan Fibonacci-sekvenssin mukaan Fibonacci-kasa tarjoaa paremmat käyttöajat monille operaatioille verrattuna binääri- tai binomiaalisiin kasoihin. Ne ovat erityisen hyödyllisiä verkon optimointialgoritmeissa.

Python's Heap -toteutus – The kasaq Moduulit

Python tarjoaa sisäänrakennetun moduulin kasatoimintoihin - the heapq moduuli. Tämä moduuli tarjoaa kokoelman kekoon liittyviä toimintoja, joiden avulla kehittäjät voivat muuntaa luettelot kasoiksi ja suorittaa erilaisia ​​kasotoimintoja ilman mukautettua toteutusta. Sukellaanpa tämän moduulin vivahteisiin ja siihen, kuinka se tuo sinulle kasojen voiman.

- heapq moduuli ei tarjoa erillistä keon tietotyyppiä. Sen sijaan se tarjoaa toimintoja, jotka toimivat tavallisissa Python-listoissa, muuntavat ja käsittelevät niitä binäärikasat.

Tämä lähestymistapa on sekä muistitehokas että integroituu saumattomasti Pythonin olemassa oleviin tietorakenteisiin.

Se tarkoittaa sitä kasat esitetään luetteloina in heapq. Tämän esityksen kauneus on sen yksinkertaisuus – nollapohjainen listaindeksijärjestelmä toimii implisiittisenä binääripuuna. Jokaiselle tietylle elementille sijainnissa i, sen:

• Vasen lapsi on paikallaan 2*i + 1
• Oikea lapsi on paikallaan 2*i + 2
• Pääsolmu on paikassa (i-1)//2

Tämä implisiittinen rakenne varmistaa, että erillistä solmupohjaista binaaripuuesitystä ei tarvita, mikä tekee toiminnoista yksinkertaista ja muistin käytön minimaalisen.

On tärkeää huomata, että heapq moduuli luo oletuksena min kasoja. Tämä tarkoittaa, että pienin elementti on aina juuressa (tai listan ensimmäisellä paikalla). Jos tarvitset maksimikeon, sinun on käännettävä järjestys kertomalla elementit -1 tai käytä mukautettua vertailutoimintoa.

Pythonin heapq moduuli tarjoaa joukon toimintoja, joiden avulla kehittäjät voivat suorittaa erilaisia ​​kasatoimintoja listoille.

Seuraavissa osissa sukeltamme syvälle jokaiseen näistä perustoimintoihin tutkimalla niiden mekaniikkaa ja käyttötapauksia.

Kuinka muuttaa luettelo keoksi

- heapify() -toiminto on monien pinoon liittyvien tehtävien lähtökohta. Se kestää iteroitavan (yleensä luettelon) ja järjestää sen elementit uudelleen paikoilleen täyttämään minimikeon ominaisuudet:

import heapq data = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]
heapq.heapify(data)
print(data)

Tämä tulostaa uudelleen järjestetyn luettelon, joka edustaa kelvollista minimikekoa:

[1, 1, 2, 3, 3, 9, 4, 6, 5, 5, 5]

Kuinka lisätä elementti kasaan

- heappush() toiminnon avulla voit lisätä uuden elementin kasaan säilyttäen samalla keon ominaisuudet:

import heapq heap = []
heapq.heappush(heap, 5)
heapq.heappush(heap, 3)
heapq.heappush(heap, 7)
print(heap)

Koodin suorittaminen antaa sinulle luettelon elementeistä, jotka ylläpitävät minimikeon ominaisuutta:

[3, 5, 7]

Kuinka poistaa ja palauttaa pienin elementti kasasta

- heappop() funktio poimii ja palauttaa kasan pienimmän elementin (min-keon juuri). Poistamisen jälkeen se varmistaa, että luettelo pysyy kelvollisena kasana:

import heapq heap = [1, 3, 5, 7, 9]
print(heapq.heappop(heap))
print(heap)

Tämä tulostaa pienimmän elementin ja jäljellä olevan luettelon:

1
[3, 7, 5, 9]

Täällä 1 on pienin elementti heap, ja jäljellä oleva luettelo on säilyttänyt keon ominaisuuden myös poistamisen jälkeen 1.

Kuinka työntää uusi kohde ja pop pienin esine

- heappushpop() -toiminto on yhdistetty toiminto, joka työntää uuden kohteen kasaan ja sitten ponnahtaa ja palauttaa kasan pienimmän kohteen:

import heapq heap = [3, 5, 7, 9]
print(heapq.heappushpop(heap, 4)) print(heap)

Tämä tulee näkyviin 3, pienin elementti ja tulosta uusi heap luettelo, joka nyt sisältää 4 säilyttäen samalla kasan ominaisuuden:

3
[4, 5, 7, 9]

Kuinka korvata pienin esine ja työntää uusi kohde

- heapreplace() toiminto ponnahtaa pienimmän elementin ja työntää uuden elementin kasaan, kaikki yhdellä tehokkaalla toiminnolla:

import heapq heap = [1, 5, 7, 9]
print(heapq.heapreplace(heap, 4))
print(heap)

Tämä tulostuu 1, pienin elementti, ja luettelo sisältää nyt 4 ja säilyttää keon ominaisuuden:

1
[4, 5, 7, 9]

Useiden ääripäiden löytäminen Pythonin kasasta

nlargest(n, iterable[, key]) ja nsmallest(n, iterable[, key]) funktiot on suunniteltu hakemaan useita suurimpia tai pienimpiä elementtejä iteroitavasta. Ne voivat olla tehokkaampia kuin koko iteroitavan lajittelu, kun tarvitset vain muutaman ääriarvon. Oletetaan esimerkiksi, että sinulla on seuraava luettelo ja haluat löytää luettelosta kolme pienintä ja kolme suurinta arvoa:

data = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]

Täällä nlargest() ja nsmallest() toiminnot voivat olla hyödyllisiä:

import heapq data = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]
print(heapq.nlargest(3, data)) print(heapq.nsmallest(3, data)) 

Tämä antaa sinulle kaksi luetteloa – yksi sisältää kolme suurinta arvoa ja toinen sisältää kolme pienintä arvoa data lista:

[9, 6, 5]
[1, 1, 2]

Kuinka rakentaa mukautettu kasasi

Pythonin aikana heapq moduuli tarjoaa vankan joukon työkaluja kasojen kanssa työskentelyyn. On tilanteita, joissa oletusarvoinen min-keon toiminta ei ehkä riitä. Haluatpa ottaa käyttöön maksimikeon tai tarvitsetko keon, joka toimii mukautettujen vertailutoimintojen perusteella, mukautetun kasan rakentaminen voi olla vastaus. Tutkitaan kuinka räätälöidä kasoja tiettyjen tarpeiden mukaan.

Max-keon toteuttaminen käyttämällä heapq

Oletusarvoisesti heapq luo min kasoja. Yksinkertaisella tempulla voit kuitenkin käyttää sitä toteuttamaan maksimikasan. Ajatuksena on kääntää elementtien järjestys kertomalla ne -1 ennen kuin lisäät ne kasaan:

import heapq class MaxHeap: def __init__(self): self.heap = [] def push(self, val): heapq.heappush(self.heap, -val) def pop(self): return -heapq.heappop(self.heap) def peek(self): return -self.heap[0]

Tällä lähestymistavalla suurimmasta luvusta (absoluuttisen arvon mukaan) tulee pienin, mikä mahdollistaa heapq toimii maksimikekorakenteen ylläpitämiseksi.

Kasat mukautetuilla vertailutoiminnoilla

Joskus saatat tarvita kasan, joka ei vain vertaile elementtien luonnollisen järjestyksen perusteella. Jos esimerkiksi työskentelet monimutkaisten objektien kanssa tai sinulla on tietyt lajittelukriteerit, mukautettu vertailutoiminto tulee välttämättömäksi.

Tämän saavuttamiseksi voit kääriä elementit auttajaluokkaan, joka ohittaa vertailuoperaattorit:

import heapq class CustomElement: def __init__(self, obj, comparator): self.obj = obj self.comparator = comparator def __lt__(self, other): return self.comparator(self.obj, other.obj) def custom_heappush(heap, obj, comparator=lambda x, y: x < y): heapq.heappush(heap, CustomElement(obj, comparator)) def custom_heappop(heap): return heapq.heappop(heap).obj

Tällä asetuksella voit määrittää minkä tahansa mukautetun vertailufunktion ja käyttää sitä kasan kanssa.

Yhteenveto

Kasat tarjoavat ennustettavan suorituskyvyn monille toiminnoille, mikä tekee niistä luotettavan valinnan tärkeysperusteisiin tehtäviin. On kuitenkin tärkeää ottaa huomioon kulloisenkin sovelluksen erityisvaatimukset ja ominaisuudet. Joissakin tapauksissa keon toteutuksen säätäminen tai jopa vaihtoehtoisten tietorakenteiden valitseminen saattaa tuottaa paremman suorituskyvyn todellisessa maailmassa.

Kuten olemme käyneet läpi, kasat ovat enemmän kuin vain yksi tietorakenne. Ne edustavat tehokkuuden, rakenteen ja sopeutumiskyvyn yhdistelmää. Niiden perusominaisuuksista niiden toteutukseen Pythonissa heapq moduuli, kasat tarjoavat vankan ratkaisun lukemattomiin laskennallisiin haasteisiin, erityisesti niihin, jotka keskittyvät prioriteettiin.

• SEO-pohjainen sisällön ja PR-jakelu. Vahvista jo tänään.
• PlatoData.Network Vertical Generatiivinen Ai. Vahvista itseäsi. Pääsy tästä.
• PlatoAiStream. Web3 Intelligence. Tietoa laajennettu. Pääsy tästä.
• PlatoESG. hiili, CleanTech, energia, ympäristö, Aurinko, Jätehuolto. Pääsy tästä.
• PlatonHealth. Biotekniikan ja kliinisten kokeiden älykkyys. Pääsy tästä.
• Lähde: https://stackabuse.com/guide-to-heaps-in-python/