Juhend kuhjade kohta Pythonis

Sissejuhatus

Kujutage ette elavat lennujaama, kus iga minut tõusevad ja maanduvad lennud. Nii nagu lennujuhid prioriseerivad lende kiireloomulisuse alusel, aitavad kuhjad meil konkreetsete kriteeriumide alusel andmeid hallata ja töödelda, tagades, et kõige kiireloomulisemad või olulisemad andmed on alati üleval juurdepääsetavad.

Selles juhendis alustame teekonda, et mõista hunnikuid juba maast madalast. Alustuseks selgitame välja, mis on kuhjad ja nende olemuslikud omadused. Sealt edasi sukeldume Pythoni enda kuhjade rakendusse, the heapq moodulit ja uurige selle rikkalikku funktsioonide komplekti. Seega, kui olete kunagi mõelnud, kuidas tõhusalt hallata dünaamilist andmekogumit, kus sageli vajatakse kõrgeima (või madalaima) prioriteediga elementi, siis on teil hea meel.

Mis on hunnik?

Esimene asi, mida soovite enne hunnikute kasutamisesse sukeldumist mõista, on mis on hunnik. Hunnik paistab andmestruktuuride maailmas silma puupõhise jõuallikana, mis on selles eriti vilunud korra ja hierarhia hoidmine. Kuigi harjumatu silma jaoks võib see sarnaneda kahendpuuga, eristavad selle struktuuri ja reguleerivate reeglite nüansid selgelt.

Üks kuhja määravaid omadusi on selle olemus a täielik binaarne puu. See tähendab, et puu iga tasand, välja arvatud ehk viimane, on täielikult täidetud. Sellel viimasel tasemel paiknevad sõlmed vasakult paremale. Selline struktuur tagab, et hunnikuid saab tõhusalt esitada ja töödelda massiivide või loendite abil, kusjuures iga elemendi asukoht massiivis peegeldab selle paigutust puus.

Kuhja tõeline olemus peitub aga selles tellimine. Sees max kuhjaga, ületab mis tahes antud sõlme väärtus oma alamväärtusi või on nendega võrdne, asetades suurima elemendi otse juure. Teisest küljest a min hunnik toimib vastupidisel põhimõttel: mis tahes sõlme väärtus on väiksem või võrdne selle laste väärtustega, tagades, et väikseim element asub juurtes.

Edenedes sukeldume sügavamale sellesse, kuidas need hunnikutele omased omadused võimaldavad tõhusaid toiminguid ja kuidas Pythoni heapq moodul integreerib sujuvalt hunnikuid meie kodeerimispüüdlustesse.

Kuhjade omadused ja omadused

Ainulaadse struktuuri ja järjestamispõhimõtetega kuhjad toovad esile mitmeid erinevaid omadusi ja omadusi, mis muudavad need erinevates arvutusstsenaariumides hindamatuks.

Ennekõike on kuhjad olemuselt tõhus. Nende puupõhine struktuur, täpsemalt täielik binaarpuu vorming, tagab, et selliseid toiminguid nagu prioriteetsete elementide (maksimaalne või minimaalne) sisestamine ja ekstraheerimine saab sooritada tavaliselt logaritmilise aja jooksul. O (log n). See tõhusus on õnnistuseks algoritmidele ja rakendustele, mis nõuavad sagedast juurdepääsu prioriteetsetele elementidele.

Veel üks tähelepanuväärne hunnikute omadus on nende mälu tõhusus. Kuna hunnikuid saab esitada massiivide või loendite abil, ilma et oleks vaja selgesõnalisi viiteid alam- või ülemsõlmedele, säästavad need ruumi. Iga elemendi asukoht massiivis vastab selle paigutusele puus, võimaldades prognoositavat ja otsest läbimist ja manipuleerimist.

Selle tagab kuhjade järjestusomadus, olgu see siis max hunnikuna või min hunnikuna juur omab alati kõrgeima prioriteediga elementi. See ühtlane järjestamine võimaldab kiiret juurdepääsu kõrgeima prioriteediga elemendile, ilma et peaksite kogu struktuurist läbi otsima.

Lisaks on hunnikuid mitmekülgne. Kui binaarsed kuhjad (kus kummalgi vanemal on maksimaalselt kaks last) on kõige levinumad, võib hunnikuid üldistada nii, et neil on rohkem kui kaks last. d-aari kuhjad. See paindlikkus võimaldab peenhäälestada konkreetsete kasutusjuhtude ja jõudlusnõuete alusel.

Lõpuks on hunnikud isereguleeruv. Kui elemente lisatakse või eemaldatakse, korraldab struktuur end ümber, et säilitada oma omadused. See dünaamiline tasakaalustamine tagab, et hunnik jääb alati oma põhitoimingute jaoks optimeerituks.

Kui me süveneme Pythoni juurutusse ja praktilistesse rakendustesse, avaneb meie ees kuhjade tõeline potentsiaal.

Kuhjade tüübid

Kõik kuhjad pole võrdsed. Olenevalt nende järjestusest ja konstruktsiooni omadustest saab hunnikuid liigitada eri tüüpidesse, millest igaühel on oma kasutusvõimalused ja eelised. Kaks peamist kategooriat on max kuhjaga ja min hunnik.

Kõige eristavam tunnus a max kuhjaga on see, et mis tahes antud sõlme väärtus on suurem või võrdne selle laste väärtustega. See tagab, et kuhja suurim element asub alati juurtes. Selline struktuur on eriti kasulik siis, kui on vaja sageli juurde pääseda maksimaalsele elemendile, nagu teatud prioriteetse järjekorra rakendustes.

Maksimaalse hunniku vaste, a min hunnik tagab, et mis tahes antud sõlme väärtus on väiksem või võrdne selle laste väärtustega. See asetab kuhja väikseima elemendi juure. Minimaalsed kuhjad on hindamatud stsenaariumide puhul, kus kõige väiksem element on esmatähtis, näiteks algoritmides, mis tegelevad reaalajas andmetöötlusega.

Lisaks nendele põhikategooriatele saab hunnikuid eristada ka nende hargnemisteguri alusel:

Kui binaarsed kuhjad on kõige levinumad, kusjuures kummalgi vanemal on maksimaalselt kaks last, saab kuhjade mõistet laiendada ka sõlmedele, millel on rohkem kui kaks last. Sees d-aari hunnik, on igal sõlmel maksimaalselt d lapsed. Seda variatsiooni saab optimeerida konkreetsete stsenaariumide jaoks, näiteks puu kõrguse vähendamine teatud toimingute kiirendamiseks.

Binoomkuhja on rekursiivselt määratletud binoompuude kogum. Binoomkuhjasid kasutatakse prioriteetsete järjekordade juurutamisel ja need pakuvad tõhusaid liitmistoiminguid.

Kuulsa Fibonacci jada järgi nime saanud Fibonacci hunnik pakub paljude operatsioonide jaoks paremini amortiseerunud tööaega võrreldes kahend- või binoomkuhjadega. Need on eriti kasulikud võrgu optimeerimise algoritmides.

Pythoni kuhja juurutamine – The kuhjaq moodulid

Python pakub kuhjaoperatsioonide jaoks sisseehitatud moodulit – the heapq moodul. See moodul pakub hunnikutega seotud funktsioonide kogumit, mis võimaldab arendajatel muuta loendeid hunnikuteks ja teha erinevaid kuhjaoperatsioone, ilma et oleks vaja kohandatud rakendust. Sukeldume selle mooduli nüanssidesse ja sellesse, kuidas see teieni toob kuhjade jõu.

. heapq moodul ei paku erinevat hunniku andmetüüpi. Selle asemel pakub see funktsioone, mis töötavad tavalistes Pythoni loendites, teisendades ja käsitledes neid kui binaarsed kuhjad.

See lähenemisviis on nii mälutõhus kui ka integreerub sujuvalt Pythoni olemasolevate andmestruktuuridega.

See tähendab seda kuhjad on esitatud loenditena in heapq. Selle esituse ilu seisneb selle lihtsuses – nullipõhine loendiindeksisüsteem toimib kaudse kahendpuuna. Iga elemendi jaoks positsioonis i, selle:

• Vasak laps on positsioonis 2*i + 1
• Parem laps on asendis 2*i + 2
• Vanemsõlm on asukohas (i-1)//2

See kaudne struktuur tagab, et puudub vajadus eraldi sõlmepõhise binaarpuu esituse järele, muutes toimingud lihtsaks ja mälukasutuse minimaalseks.

Oluline on märkida, et heapq moodul loob vaikimisi min hunnikuid. See tähendab, et väikseim element on alati juurtes (või loendis esimesel kohal). Kui vajate maksimaalset hunnikut, peate järjekorra ümber pöörama, korrutades elemendid arvuga -1 või kasutage kohandatud võrdlusfunktsiooni.

Pythoni oma heapq moodul pakub komplekti funktsioone, mis võimaldavad arendajatel teha loenditega erinevaid kuhjaoperatsioone.

Järgmistes osades käsitleme kõiki neid põhitoiminguid põhjalikult, uurides nende mehaanikat ja kasutusjuhtumeid.

Kuidas muuta loend hunnikuks

. heapify() funktsioon on paljude kuhjaga seotud ülesannete lähtepunkt. See võtab itereeritava (tavaliselt loendi) ja korraldab selle elemendid paigas ümber, et rahuldada minimaalse hunniku omadusi:

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

See väljastab ümberjärjestatud loendi, mis esindab kehtivat minimaalset hunnikut:

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

Kuidas hunnikusse elementi lisada

. heappush() funktsioon võimaldab lisada hunnikusse uue elemendi, säilitades samal ajal kuhja omadused:

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

Koodi käivitamine annab teile loendi elementidest, mis säilitavad atribuuti min hunnik:

[3, 5, 7]

Kuidas eemaldada ja tagastada hunnikust väikseim element

. heappop() funktsioon eraldab ja tagastab kuhjast väikseima elemendi (min kuhja juur). Pärast eemaldamist tagab see, et loend jääb kehtivaks hunnikuks:

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

See väljastab väikseima elemendi ja ülejäänud loendi:

1
[3, 7, 5, 9]

Siin 1 on väikseim element heap, ja ülejäänud loend on säilitanud kuhja atribuudi isegi pärast eemaldamist 1.

Kuidas lükata uut eset ja poputada väikseim üksus

. heappushpop() Funktsioon on kombineeritud toiming, mis surub hunnikusse uue üksuse ning seejärel hüppab ja tagastab hunnikust väikseima üksuse:

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

See väljub 3, väikseim element ja printige välja uus heap nimekiri, mis nüüd sisaldab 4 kuhja omaduse säilitamisel:

3
[4, 5, 7, 9]

Kuidas asendada väikseim üksus ja lükata uus üksus

. heapreplace() funktsioon hüppab väikseima elemendi ja lükkab hunnikusse uue elemendi, seda kõike ühe tõhusa toiminguga:

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

See prindib 1, väikseim element ja loend sisaldab nüüd 4 ja säilitab kuhja omaduse:

1
[4, 5, 7, 9]

Mitme äärmuse leidmine Pythoni hunnikus

nlargest(n, iterable[, key]) ja nsmallest(n, iterable[, key]) funktsioonid on loodud itereeritavast mitme suurima või väiksema elemendi hankimiseks. Need võivad olla tõhusamad kui kogu itereeritava osa sorteerimine, kui vajate vaid mõnda äärmuslikku väärtust. Oletame näiteks, et teil on järgmine loend ja soovite leida loendist kolm väikseimat ja kolm suurimat väärtust:

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

Siin nlargest() ja nsmallest() funktsioonid võivad kasuks tulla:

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

See annab teile kaks loendit – üks sisaldab kolme suurimat väärtust ja teine ​​kolme väikseimat väärtust data nimekiri:

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

Kuidas luua oma kohandatud hunnik

Kuigi Pythoni oma heapq moodul pakub tugevat tööriistakomplekti kuhjadega töötamiseks, on stsenaariume, kus vaikimisi minimaalse hunniku käitumisest ei pruugi piisata. Ükskõik, kas soovite rakendada maksimaalset hunnikut või vajate kohandatud võrdlusfunktsioonidel põhinevat hunnikut, võib vastuseks olla kohandatud hunniku loomine. Uurime, kuidas hunnikuid konkreetsetele vajadustele kohandada.

Max Heap'i rakendamine kasutades heapq

Vaikimisi heapq loob min hunnikuid. Kuid lihtsa nipi abil saate seda kasutada maksimaalse hunniku rakendamiseks. Idee on elementide järjekord ümber pöörata, korrutades need arvuga -1 enne nende hunnikusse lisamist:

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]

Selle lähenemisviisi korral muutub suurim arv (absoluutväärtuses) väikseimaks, mis võimaldab heapq funktsioonid maksimaalse hunniku struktuuri säilitamiseks.

Kuhjad kohandatud võrdlusfunktsioonidega

Mõnikord võib vaja minna hunnikut, mis ei võrdle ainult elementide loomulikku järjestust. Näiteks kui töötate keerukate objektidega või teil on kindlad sortimiskriteeriumid, muutub kohandatud võrdlusfunktsioon hädavajalikuks.

Selle saavutamiseks saate mähkida elemendid abiklassi, mis alistab võrdlustehtereid:

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

Selle seadistuse abil saate määratleda mis tahes kohandatud võrdlusfunktsiooni ja kasutada seda koos kuhjaga.

Järeldus

Kuhjad pakuvad prognoositavat jõudlust paljude toimingute jaoks, muutes need prioriteedipõhiste ülesannete jaoks usaldusväärseks valikuks. Siiski on oluline arvestada konkreetse rakenduse konkreetseid nõudeid ja omadusi. Mõnel juhul võib hunniku juurutamise kohandamine või isegi alternatiivsete andmestruktuuride valimine anda parema reaalse jõudluse.

Kuhjad, nagu oleme läbi teinud, on midagi enamat kui lihtsalt üks andmestruktuur. Need esindavad tõhususe, struktuuri ja kohanemisvõime ühinemist. Alates nende põhiomadustest kuni nende rakendamiseni Pythonis heapq moodul, kuhjad pakuvad tugevat lahendust arvukatele arvutusprobleemidele, eriti neile, mis keskenduvad prioriteedile.

• SEO-põhise sisu ja PR-levi. Võimenduge juba täna.
• PlatoData.Network Vertikaalne generatiivne Ai. Jõustage ennast. Juurdepääs siia.
• PlatoAiStream. Web3 luure. Täiustatud teadmised. Juurdepääs siia.
• PlatoESG. Süsinik, CleanTech, Energia, Keskkond päikeseenergia, Jäätmekäitluse. Juurdepääs siia.
• PlatoTervis. Biotehnoloogia ja kliiniliste uuringute luureandmed. Juurdepääs siia.
• Allikas: https://stackabuse.com/guide-to-heaps-in-python/