Python.
Skapa en enkel hög
De heapify (iterbar) :- Denna funktion används för att konvertera det iterable till en hög datastruktur. dvs i högordning.
Python3
# importing 'heapq' to implement heap queue> import> heapq> # initializing list> li>=> [>5>,>7>,>9>,>1>,>3>]> # using heapify to convert list into heap> heapq.heapify(li)> # printing created heap> print> (>'The created heap is : '>,(>list>(li)))> |
>
>
skal sorteraProduktion
The created heap is : [1, 3, 9, 7, 5]>
Lägga till och poppa objekt effektivt
- heappush(heap, ele) : Denna funktion används för att infoga elementet som nämns i dess argument i en heap. De ordningen justeras, så att högstrukturen bibehålls. heappop(heap) : Denna funktion används för att ta bort och returnera det minsta elementet från högen. Ordningen justeras, så att högstrukturen bibehålls.
Python3
# importing 'heapq' to implement heap queue> import> heapq> # initializing list> li>=> [>5>,>7>,>9>,>1>,>3>]> # using heapify to convert list into heap> heapq.heapify(li)> # printing created heap> print>(>'The created heap is : '>, end>=>'')> print>(>list>(li))> # using heappush() to push elements into heap> # pushes 4> heapq.heappush(li,>4>)> # printing modified heap> print>(>'The modified heap after push is : '>, end>=>'')> print>(>list>(li))> # using heappop() to pop smallest element> print>(>'The popped and smallest element is : '>, end>=>'')> print>(heapq.heappop(li))> |
>
>Produktion
The created heap is : [1, 3, 9, 7, 5] The modified heap after push is : [1, 3, 4, 7, 5, 9] The popped and smallest element is : 1>
Lägger till och poppar samtidigt
- heappushpop(heap, ele):- Denna funktion kombinerar funktionen av både push- och pop-operationer i ett uttalande, vilket ökar effektiviteten. Högordningen bibehålls efter denna operation. heapreplace(heap, ele):- Den här funktionen infogar och poppar också element i en sats, men den skiljer sig från ovanstående funktion. I detta trycks elementet först, sedan skjuts elementet. dvs värdet som är större än det tryckta värdet kan returneras. heapreplace() returnerar det minsta värdet ursprungligen i högen oavsett det pushade elementet i motsats till heappushpop().
Python3
# importing 'heapq' to implement heap queue> import> heapq> # initializing list 1> li1>=> [>5>,>1>,>9>,>4>,>3>]> # initializing list 2> li2>=> [>5>,>7>,>9>,>4>,>3>]> # using heapify() to convert list into heap> heapq.heapify(li1)> heapq.heapify(li2)> # using heappushpop() to push and pop items simultaneously> # pops 2> print>(>'The popped item using heappushpop() is : '>, end>=>'')> print>(heapq.heappushpop(li1,>2>))> # using heapreplace() to push and pop items simultaneously> # pops 3> print>(>'The popped item using heapreplace() is : '>, end>=>'')> print>(heapq.heapreplace(li2,>2>))> |
>
>Produktion
The popped item using heappushpop() is : 1 The popped item using heapreplace() is : 3>
Hitta de största och minsta elementen från Heap i Python
- nlargest(k, iterable, key = fun) : Denna funktion används för att returnera de k största elementen från den iterable som anges och uppfylla nyckeln om den nämns. nsmallest(k, iterable, key = fun) : Denna funktion används för att returnera de k minsta elementen från den iterable som anges och uppfylla nyckeln om den nämns.
Python3
# Python code to demonstrate working of> # nlargest() and nsmallest()> # importing 'heapq' to implement heap queue> import> heapq> # initializing list> li1>=> [>6>,>7>,>9>,>4>,>3>,>5>,>8>,>10>,>1>]> # using heapify() to convert list into heap> heapq.heapify(li1)> # using nlargest to print 3 largest numbers> # prints 10, 9 and 8> print>(>'The 3 largest numbers in list are : '>, end>=>'')> print>(heapq.nlargest(>3>, li1))> # using nsmallest to print 3 smallest numbers> # prints 1, 3 and 4> print>(>'The 3 smallest numbers in list are : '>, end>=>'')> print>(heapq.nsmallest(>3>, li1))> |
>
>Produktion
The 3 largest numbers in list are : [10, 9, 8] The 3 smallest numbers in list are : [1, 3, 4]>
Exempel:
Python3
sträng hitta c++
import> heapq> # Initialize a list with some values> values>=> [>5>,>1>,>3>,>7>,>4>,>2>]> # Convert the list into a heap> heapq.heapify(values)> # Print the heap> print>(>'Heap:'>, values)> # Add a new value to the heap> heapq.heappush(values,>6>)> # Print the updated heap> print>(>'Heap after push:'>, values)> # Remove and return the smallest element from the heap> smallest>=> heapq.heappop(values)> # Print the smallest element and the updated heap> print>(>'Smallest element:'>, smallest)> print>(>'Heap after pop:'>, values)> # Get the n smallest elements from the heap> n_smallest>=> heapq.nsmallest(>3>, values)> # Print the n smallest elements> print>(>'Smallest 3 elements:'>, n_smallest)> # Get the n largest elements from the heap> n_largest>=> heapq.nlargest(>2>, values)> # Print the n largest elements> print>(>'Largest 2 elements:'>, n_largest)> |
>
>Produktion
Heap: [1, 4, 2, 7, 5, 3] Heap after push: [1, 4, 2, 7, 5, 3, 6] Smallest element: 1 Heap after pop: [2, 4, 3, 7, 5, 6] Smallest 3 elements: [2, 3, 4] Largest 2 elements: [7, 6]>
Det här programmet skapar en heap-kö med hjälp av heapq-modulen i Python och utför olika operationer som att konvertera en lista till en heap, lägga till ett nytt värde till heapen, ta bort det minsta elementet från heapen, hämta de n minsta och n största elementen från högen.
Notera att heapq-modulen i Python tillhandahåller funktioner för att utföra heap-operationer på listor på plats, utan att skapa en separat datastruktur för heapen. Heapq-modulen är effektiv och lätt att använda, vilket gör den till ett populärt val för att implementera prioriterade köer och andra datastrukturer i Python.
Fördelar med att använda en heap-kö (eller heapq) i Python:
- Effektiv : En heap-kö är en mycket effektiv datastruktur för att hantera prioriterade köer och heaps i Python. Det ger logaritmisk tidskomplexitet för många operationer, vilket gör det till ett populärt val för många applikationer. Utrymmeseffektiv : Högköer är utrymmeseffektiva, eftersom de lagrar element i en arraybaserad representation, vilket minimerar den overhead som är associerad med nodbaserade datastrukturer som länkade listor. Lätt att använda: Heap-köer i Python är lätta att använda, med ett enkelt och intuitivt API som gör det enkelt att utföra grundläggande operationer som att infoga, ta bort och hämta element från heapen. Flexibel : Högköer i Python kan användas för att implementera olika datastrukturer som prioriterade köer, heaps och binära träd, vilket gör dem till ett mångsidigt verktyg för många applikationer.
Nackdelar med att använda en heap-kö (eller heapq) i Python:
- Begränsad funktionalitet : Heap-köer är främst designade för att hantera prioriterade köer och heaps, och kanske inte är lämpliga för mer komplexa datastrukturer och algoritmer. Ingen slumpmässig åtkomst : Högköer stöder inte slumpmässig åtkomst till element, vilket gör det svårt att komma åt element i mitten av högen eller modifiera element som inte är överst i högen. Ingen sortering: Högköer stöder inte sortering, så om du behöver sortera element i en specifik ordning måste du använda en annan datastruktur eller algoritm. Inte trådsäkra : Högköer är inte trådsäkra, vilket innebär att de kanske inte är lämpliga för användning i flertrådade applikationer där datasynkronisering är kritisk.
Överlag är heap-köer en mycket effektiv och flexibel datastruktur för att hantera prioriterade köer och heaps i Python, men kan ha begränsad funktionalitet och kanske inte lämpar sig för alla applikationer.