Útmutató a Python kupacokhoz

Bevezetés

Képzeljen el egy nyüzsgő repülőteret, ahol percenként szállnak fel és szállnak le járatok. Ahogy a légiforgalmi irányítók a sürgősségi szempontok alapján rangsorolják a repüléseket, a halmok segítenek nekünk az adatok meghatározott kritériumok alapján történő kezelésében és feldolgozásában, biztosítva, hogy a „legsürgősebb” vagy „fontosabb” adatok mindig a legfelül elérhetők legyenek.

Ebben az útmutatóban egy utazásra indulunk, hogy az alapoktól kezdve megértsük a kupacokat. Kezdjük azzal, hogy tisztázzuk, mi is azok a kupacok, és melyek azok rejlő tulajdonságai. Innentől kezdve a Python saját halommegvalósításába, a heapq modult, és fedezze fel gazdag funkciókészletét. Tehát, ha valaha is azon töprengett, hogyan kezelhet hatékonyan egy dinamikus adathalmazt, ahol gyakran a legmagasabb (vagy legalacsonyabb) prioritású elemre van szükség, akkor egy csemege.

Mi az a kupac?

Az első dolog, amit meg szeretne érteni, mielőtt belemerülne a kupacok használatába mi az a kupac. Az adatstruktúrák világában egy halom fa alapú erőműként emelkedik ki, amelyben különösen jártas a rend és a hierarchia fenntartása. Bár gyakorlatlan szemmel bináris fára hasonlíthat, szerkezetének és szabályainak árnyalatai egyértelműen megkülönböztetik egymástól.

A kupac egyik meghatározó jellemzője, hogy a teljes bináris fa. Ez azt jelenti, hogy a fa minden szintje, kivéve talán az utolsót, teljesen kitöltött. Ezen az utolsó szinten a csomópontok balról jobbra töltődnek fel. Egy ilyen struktúra biztosítja, hogy a kupacokat hatékonyan lehessen ábrázolni és tömbök vagy listák segítségével manipulálni lehessen úgy, hogy a tömbben minden egyes elem pozíciója tükrözi a fában elfoglalt helyét.

A kupac valódi lényege azonban abban rejlik rendelés. egy max halom, bármely adott csomópont értéke meghaladja a gyermekei értékeit vagy megegyezik azokkal, és a legnagyobb elemet közvetlenül a gyökérben helyezi el. Másrészt a min kupac ellentétes elven működik: bármely csomópont értéke kisebb vagy egyenlő a gyermekértékekkel, így biztosítva, hogy a legkisebb elem a gyökérben üljön.

Ahogy haladunk előre, egyre mélyebbre merülünk abban, hogy a kupacok ezek a benne rejlő tulajdonságai hogyan teszik lehetővé a hatékony műveleteket, és hogyan teszik lehetővé a Python heapq modul zökkenőmentesen integrálja a kupacokat kódolási törekvéseinkbe.

A kupacok jellemzői és tulajdonságai

A kupacok egyedi felépítésükkel és rendezési elvükkel olyan különálló jellemzőket és tulajdonságokat hoznak létre, amelyek felbecsülhetetlenné teszik őket a különböző számítási forgatókönyvekben.

Az első és legfontosabb, hogy a kupacok eredendően hatékony. Fa alapú struktúrájuk, különösen a teljes bináris fa formátum biztosítja, hogy az olyan műveletek, mint a prioritást élvező elemek (maximum vagy minimum) beszúrása és kinyerése, logaritmikus időben hajthatók végre. O (log n). Ez a hatékonyság áldás az olyan algoritmusok és alkalmazások számára, amelyek gyakori hozzáférést igényelnek a prioritást élvező elemekhez.

A halmok másik figyelemre méltó tulajdonsága az memória hatékonysága. Mivel a kupacok tömbök vagy listák segítségével ábrázolhatók anélkül, hogy explicit mutatók kellenek a gyermek- vagy szülőcsomópontokhoz, helytakarékosak. Minden elem pozíciója a tömbben megfelel a fában elfoglalt helyének, lehetővé téve a kiszámítható és egyszerű bejárást és manipulációt.

A kupacok rendezési tulajdonsága, legyen az max kupac vagy min kupac, ezt biztosítja a gyökér mindig a legmagasabb prioritású elemet tartalmazza. Ez a következetes rendezés az, ami lehetővé teszi a gyors hozzáférést a kiemelt fontosságú elemhez anélkül, hogy a teljes struktúrában végig kellene keresni.

Továbbá kupacok vannak sokoldalú. Míg a bináris kupacok (ahol minden szülőnek legfeljebb két gyermeke van) a leggyakoribbak, a kupacok általánosíthatók kettőnél több gyermekre is. d-ári kupacok. Ez a rugalmasság lehetővé teszi az egyedi használati esetek és teljesítménykövetelmények alapján történő finomhangolást.

Végül a kupacok önbeállító. Amikor elemeket adunk hozzá vagy eltávolítunk, a szerkezet átrendezi magát, hogy megőrizze tulajdonságait. Ez a dinamikus kiegyensúlyozás biztosítja, hogy a kupac mindig optimalizálva maradjon az alapvető műveletekhez.

Ahogy mélyebben elmélyülünk a Python megvalósításában és gyakorlati alkalmazásaiban, a kupacokban rejlő valódi lehetőségek feltárulnak előttünk.

A kupacok típusai

Nem minden kupac egyforma. Rendezési és szerkezeti tulajdonságaiktól függően a kupacok különböző típusokba sorolhatók, mindegyiknek megvan a maga alkalmazási köre és előnyei. A két fő kategória a max halom és a min kupac.

A legmegkülönböztetőbb jellemzője a max halom az, hogy bármely adott csomópont értéke nagyobb vagy egyenlő a gyermekei értékeivel. Ez biztosítja, hogy a kupac legnagyobb eleme mindig a gyökérben legyen. Ez a struktúra különösen akkor hasznos, ha gyakran kell hozzáférni a maximális elemhez, például bizonyos prioritási sor implementációkban.

A max kupac megfelelője, a min kupac biztosítja, hogy bármely adott csomópont értéke kisebb vagy egyenlő legyen a gyermekei értékeivel. Ez a halom legkisebb elemét a gyökérben helyezi el. A minimális kupacok felbecsülhetetlen értékűek olyan forgatókönyvekben, ahol a legkisebb elem elsődleges fontosságú, például a valós idejű adatfeldolgozással foglalkozó algoritmusokban.

Ezeken az elsődleges kategóriákon túlmenően a halmok elágazási tényezőjük alapján is megkülönböztethetők:

Míg a bináris kupacok a leggyakoribbak, ahol minden szülőnek legfeljebb két gyermeke van, a kupacok fogalma kiterjeszthető a kettőnél több gyerekkel rendelkező csomópontokra. Az a d-ári kupac, minden csomópontnak legfeljebb d gyermekek. Ez a változat bizonyos forgatókönyvekre optimalizálható, például a fa magasságának csökkentése bizonyos műveletek felgyorsítása érdekében.

Binomiális kupac rekurzív módon definiált binomiális fák halmaza. A binomiális kupacokat a prioritási sor implementációiban használják, és hatékony egyesítési műveleteket kínálnak.

A híres Fibonacci-szekvencia után elnevezett Fibonacci kupac jobb amortizált futási időket kínál számos művelethez, mint a bináris vagy binomiális kupacokhoz képest. Különösen hasznosak a hálózatoptimalizáló algoritmusokban.

Python's Heap implementáció – A heapq Modulok

A Python egy beépített modult kínál a kupacműveletekhez – a heapq modult. Ez a modul halomhoz kapcsolódó funkciók gyűjteményét tartalmazza, amelyek lehetővé teszik a fejlesztők számára, hogy a listákat halommá alakítsák, és különféle kupacműveleteket hajtsanak végre anélkül, hogy egyéni megvalósításra lenne szükség. Vessen egy pillantást ennek a modulnak az árnyalataiba, és nézzük meg, hogyan hozza el a halmok erejét.

A heapq modul nem biztosít külön kupac adattípust. Ehelyett olyan függvényeket kínál, amelyek normál Python-listákon működnek, átalakítva és ként kezelve azokat bináris kupacok.

Ez a megközelítés egyszerre memóriahatékony, és zökkenőmentesen integrálódik a Python meglévő adatstruktúráiba.

Ez azt jelenti a kupacok listákként vannak ábrázolva in heapq. Ennek az ábrázolásnak a szépsége az egyszerűségben rejlik – a nulla alapú listaindexrendszer implicit bináris faként szolgál. Bármely adott elemhez a pozícióban i, annak:

• A bal oldali gyermek pozícióban van 2*i + 1
• A jobb oldali gyermek pozícióban van 2*i + 2
• A szülőcsomópont pozícióban van (i-1)//2

Ez az implicit struktúra biztosítja, hogy nincs szükség külön csomópont-alapú bináris faábrázolásra, így a műveletek egyszerűek, a memóriahasználat pedig minimális.

Fontos megjegyezni, hogy a heapq modul alapértelmezés szerint minimum kupacokat hoz létre. Ez azt jelenti, hogy a legkisebb elem mindig a gyökérben van (vagy a lista első helyén). Ha max kupacra van szüksége, akkor az elemek sorrendjét meg kell szoroznia -1 vagy használjon egyéni összehasonlító funkciót.

Pythoné heapq A modul olyan funkciókat kínál, amelyek lehetővé teszik a fejlesztők számára, hogy különféle kupacműveleteket hajtsanak végre a listákon.

A következő szakaszokban ezeknek az alapvető műveleteknek a mélyére merülünk, feltárjuk azok mechanikáját és használati eseteit.

Hogyan alakítsunk át egy listát halommá

A heapify() függvény számos kupachoz kapcsolódó feladat kiindulópontja. Iterálható (általában egy lista), és a helyükön átrendezi az elemeit, hogy megfeleljen a minimális kupac tulajdonságainak:

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

Ez egy újrarendezett listát ad ki, amely egy érvényes minimális kupacot képvisel:

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

Hogyan adjunk hozzá egy elemet a kupachoz

A heappush() A funkció lehetővé teszi új elem beszúrását a kupacba, miközben megőrzi a kupac tulajdonságait:

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

A kód futtatásával megjelenik a min kupac tulajdonságot fenntartó elemek listája:

[3, 5, 7]

Hogyan távolítsuk el és küldjük vissza a legkisebb elemet a kupacból

A heappop() függvény kivonja és visszaadja a halom legkisebb elemét (a gyökér egy min kupacban). Az eltávolítás után biztosítja, hogy a lista érvényes kupac maradjon:

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

Ez kiírja a legkisebb elemet és a fennmaradó listát:

1
[3, 7, 5, 9]

Itt, 1 a legkisebb elem a heap, és a fennmaradó lista megtartotta a kupac tulajdonságot, még az eltávolítás után is 1.

Hogyan tolja be az új elemet, és nyissa ki a legkisebb elemet

A heappushpop() A függvény egy kombinált művelet, amely egy új elemet helyez a kupacba, majd felugrik, és visszaadja a halom legkisebb elemét:

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

Ez kimenet lesz 3, a legkisebb elemet, és nyomtassa ki az újat heap listát, amely most tartalmazza 4 a halom tulajdonság megőrzése mellett:

3
[4, 5, 7, 9]

Hogyan cserélje ki a legkisebb elemet és nyomja meg az új elemet

A heapreplace() A funkció a legkisebb elemet dobja fel, és egy új elemet tol a kupacba, mindezt egyetlen hatékony műveletben:

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

Ez nyomtat 1, a legkisebb elem, és a lista most 4-et tartalmaz, és fenntartja a kupac tulajdonságot:

1
[4, 5, 7, 9]

Több szélsőség megtalálása a Python kupacban

nlargest(n, iterable[, key]) és a nsmallest(n, iterable[, key]) A függvények célja több legnagyobb vagy legkisebb elem lekérése egy iterálható elemből. Hatékonyabbak lehetnek, mint a teljes iteráció rendezése, amikor csak néhány szélsőséges értékre van szükség. Tegyük fel például, hogy rendelkezik a következő listával, és három legkisebb és három legnagyobb értéket szeretne találni a listában:

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

Itt, nlargest() és a nsmallest() a funkciók jól jöhetnek:

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

Ez két listát ad – az egyik a három legnagyobb értéket, a másik pedig a három legkisebb értéket tartalmazza data lista:

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

Hogyan építsd fel egyéni kupacodat

Míg a Python heapq modul robusztus eszközkészletet biztosít a kupacokkal való munkavégzéshez, vannak olyan forgatókönyvek, amikor az alapértelmezett minimális kupac viselkedés nem biztos, hogy elegendő. Akár max. kupacot szeretne megvalósítani, akár egyéni összehasonlítási függvényeken alapuló kupacra van szüksége, az egyéni kupac felépítése lehet a válasz. Fedezzük fel, hogyan szabhatunk kupacokat az adott igényekhez.

Max Heap megvalósítása segítségével heapq

Alapértelmezésben, heapq teremt min kupacok. Egy egyszerű trükkel azonban max kupac megvalósítására használhatod. Az ötlet az, hogy megfordítsák az elemek sorrendjét úgy, hogy megszorozzák őket -1 mielőtt hozzáadná őket a kupachoz:

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]

Ezzel a megközelítéssel a legnagyobb szám (abszolút értékben) a legkisebb lesz, lehetővé téve a heapq funkciók a maximális kupacstruktúra fenntartása érdekében.

Egyedi összehasonlító funkciókkal halmok

Néha szükséged lehet egy kupacra, amely nem csak az elemek természetes sorrendje alapján hasonlít össze. Például, ha összetett objektumokkal dolgozik, vagy meghatározott rendezési feltételekkel rendelkezik, az egyéni összehasonlítási funkció elengedhetetlenné válik.

Ennek eléréséhez az elemeket egy segédosztályba csomagolhatja, amely felülbírálja az összehasonlító operátorokat:

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

Ezzel a beállítással bármilyen egyéni összehasonlító függvényt definiálhat, és használhatja a kupacokkal.

Következtetés

A kupacok kiszámítható teljesítményt kínálnak számos művelethez, így megbízható választást jelentenek a prioritásalapú feladatokhoz. Mindazonáltal elengedhetetlen figyelembe venni az adott alkalmazás speciális követelményeit és jellemzőit. Egyes esetekben a kupac megvalósításának módosítása vagy akár alternatív adatszerkezetek választása jobb valós teljesítményt eredményezhet.

A kupacok, amint azt végigjártuk, többet jelentenek puszta adatszerkezetnél. Ezek a hatékonyság, a struktúra és az alkalmazkodóképesség találkozását jelentik. Az alapvető tulajdonságaiktól a Pythonban való megvalósításukig heapq modul, a kupacok robusztus megoldást kínálnak számtalan számítási kihívásra, különösen azokra, amelyek a prioritás köré épülnek.

• SEO által támogatott tartalom és PR terjesztés. Erősödjön még ma.
• PlatoData.Network Vertical Generative Ai. Erősítse meg magát. Hozzáférés itt.
• PlatoAiStream. Web3 Intelligence. Felerősített tudás. Hozzáférés itt.
• PlatoESG. Carbon, CleanTech, Energia, Környezet, Nap, Hulladékgazdálkodás. Hozzáférés itt.
• PlatoHealth. Biotechnológiai és klinikai vizsgálatok intelligencia. Hozzáférés itt.
• Forrás: https://stackabuse.com/guide-to-heaps-in-python/