Python Heapq tilpasset komparator

Algoritmer og datastrukturkonsepter er notorisk vanskelige. Det krever tid og krefter for å finne den best lovende avklaringen til et problem. Som et resultat, hvis du blir sittende fast med implementeringen, kan du kanskje ikke fullføre oppgaven! Som et resultat vil det å vite hvordan du bruker hver av de viktigste datastrukturene og å være klar over de python-spesifikke begrensningene, få implementeringen. To lite kjente datastrukturer som er ganske effektive er hauger og prioriterte køer.

Du lærer hvordan du bruker Heapq i Python -moduler i denne guiden. Hva slags problemer kan en haug brukes til å løse? Hvordan overvinne disse problemene med Pythons Heapq -modul.

Hva er en Python Heapq -modul?

En damedatastruktur representerer en prioriteringskø. "Heapq" -pakken i Python gjør den tilgjengelig. Det særegne ved dette i Python er at det alltid dukker opp i de minste av haugstykkene (Min Heap). Heapen [0] elementet gir alltid det minste elementet.

Flere Heapq-rutiner tar en liste som en inndata og organiserer den i en min-heap-rekkefølge. En feil med disse rutinene er at de krever en liste eller til og med en samling tuples som en parameter. De lar deg ikke sammenligne andre iterabler eller gjenstander.

La oss se på noen av de grunnleggende operasjonene som Python Heapq -modulen støtter. For å få en bedre forståelse av hvordan Python Heapq -modulen fungerer, se gjennom følgende seksjoner for implementerte eksempler.

Eksempel 1:

Heapq -modulen i Python lar deg utføre Heap -operasjoner på lister. I motsetning til noen av tilleggsmodulene, spesifiserer den ingen tilpassede klasser. Python Heapq -modulen inneholder rutiner som fungerer direkte med lister.

Vanligvis blir elementer lagt til en etter en i en haug, som begynner med en tom haug. Hvis det allerede er en liste over elementer som må konverteres til en heap, kan Heapify () -funksjonen i Python Heapq -modulen brukes til å konvertere listen til en gyldig haug.

La oss se følgende kode trinn for trinn. Heapq -modulen importeres i første linje. Etter det har vi gitt listen navnet 'en.'Heapify -metoden er blitt kalt, og listen er gitt som en parameter. Endelig vises utfallet.

Importer Heapq
en = [7, 3, 8, 1, 3, 0, 2]
Heapq.Heapify (en)
trykk (en)

Utgangen fra den nevnte koden vises nedenfor.

Du kan se at til tross for at 7 forekommer etter 8, følger listen fortsatt Heap -eiendommen. For eksempel er verdien av en [2], som er 3, mindre enn verdien av en [2*2 + 2], som er 7.

Heapify (), som du kan se, oppdaterer listen på plass, men sorterer den ikke. En haug trenger ikke å ordnes for å oppfylle Heap -eiendommen. Når Heapify () brukes på en sortert liste, er rekkefølgen på elementene på listen bevart fordi hver sortert liste passer til Heap -egenskapen.

Eksempel 2:

En liste over elementer eller en liste over tuples kan sendes som en parameter til Heapq -modulfunksjoner. Som et resultat er det to alternativer for å endre sorteringsteknikken. Til sammenligning er det første trinnet å forvandle iterable til en liste over tupler/lister. Lag en innpakningsklasse som utvider ”operatøren. I dette eksemplet skal vi se på den første nevnte tilnærmingen. Denne metoden er enkel å bruke og kan brukes til å sammenligne ordbøker.

Gjør en innsats for å forstå følgende kode. Som du kan se, har vi importert Heapq -modulen og generert en ordbok kalt DICT_ONE. Etter det er listen definert for tuple -konvertering. Funksjonen HQ.Heapify (listen min) organiserer listene i en min-heap og skriver ut resultatet.

Til slutt konverterer vi listen til en ordbok og viser resultatene.

Importer Heapq som HQ
dict_one = 'z': 'sink', 'b': 'Bill', 'w': 'wicket', 'a': 'anna', 'c': 'caouch'
list_one = [(a, b) for a, b i dict_one.elementer ()]
trykk ("Før organisering:", list_one)
HQ.Heapify (list_one)
print ("Etter organisering:", list_one)
dict_one = dict (list_one)
Print ("Final Dictionary:", Dict_one)

Utgangen er festet nedenfor. Den endelige rekonverterte ordboken vises ved siden av før og etter ordnet liste.

Eksempel 3:

Vi kommer til å innlemme en innpakningsklasse i dette eksemplet. Tenk på et scenario der en klasses gjenstander må holdes i en min-heap. Tenk på en klasse som har attributter som 'Navn ", grad," DOB "(fødselsdato) og" gebyr.'Denne klassens objekter må holdes i en min-heap avhengig av deres' dob '(fødselsdato).

Vi overstyrer nå den relasjonsoperatøren ”for å sammenligne gebyret til hver student og returnere sann eller falsk.

Nedenfor er koden du kan gå gjennom trinn for trinn. Vi har importert Heapq -modulen og definerte klassen 'Student', der vi har skrevet konstruktøren og funksjonen for tilpasset utskrift. Som du ser har vi overstyrt sammenligningsoperatøren.

Vi har nå opprettet objekter for klassen og spesifisert studentens lister. Basert på DOB, koden HQ.Heapify (EMP) vil konvertere til Min-Heap. Resultatet vises i det endelige kodestykket.

Importer Heapq som HQ
Klasseelev:
def __init __ (selv, a, b, yos, c):
selv-.Navn = a
selv-.grad = b
selv-.DOB = YOS
selv-.avgift = c
def print_me (selv):
trykk ("Navn:", selv.Navn)
trykk ("grad:", selv.grad)
trykk ("Fødselsdato:", STR (selv.DOB))
trykk ("Lønn:", STR (selv.avgift))
def __lt __ (self, nxt):
Returnerer selv.DOB < nxt.DOB
STD1 = Student ('Alex', 'Law', 1990, 36000)
STD2 = Student ('Mathew', 'PhD', 1998, 35000)
STD3 = Student ('Tina', 'Computer Science', 1980, 70000)
STD4 = Student ('Jack', 'It', 1978, 90000)
STD = [STD1, STD2, STD3, STD4]
HQ.Heapify (STD)
for jeg i rekkevidde (0, len (STD)):
STD [i].print_me ()
skrive ut()

Her er den komplette utgangen av referansekoden nevnt ovenfor.

Konklusjon:

Du har nå en bedre forståelse av datastrukturer for haug og prioriteringskø og hvordan de kan hjelpe deg med å løse forskjellige typer problemer. Du studerte hvordan du genererer hauger fra Python -lister ved hjelp av Python Heapq -modulen. Du studerte også hvordan du bruker de forskjellige operasjonene av Python Heapq -modulen. For bedre å forstå emnet, les artikkelen grundig og bruk eksemplene som er gitt.