A Max-hoop is een volledige binaire boom waarin de waarde in elk intern knooppunt groter is dan of gelijk is aan de waarden in de kinderen van dat knooppunt. Het in kaart brengen van de elementen van een heap in een array is triviaal: als een knooppunt een index k heeft, wordt het linkerkind ervan opgeslagen op index 2k+1 en zijn rechterkind bij index 2k+2 .
Voorbeelden van Max Heap:
Hoe wordt Max Heap vertegenwoordigd?
Een max Heap is een complete binaire boom. Een maximale heap wordt doorgaans weergegeven als een array. Het rootelement bevindt zich op Arr[0]. Onderstaande tabel toont indexen van andere knooppunten voor het i-de knooppunt, dat wil zeggen Arr[i]:
- Arr[(i-1)/2] Geeft het bovenliggende knooppunt terug.
- Arr[(2*i)+1] Geeft het linker onderliggende knooppunt terug.
- Arr[(2*i)+2] Geeft het rechter onderliggende knooppunt terug.
Bewerkingen op Max Heap:
- getMax() : Het retourneert het hoofdelement van Max Heap. De tijdcomplexiteit van deze operatie is O(1) .
- extraheerMax() : Verwijdert het maximale element uit MaxHeap. De tijdscomplexiteit van deze operatie is O(logboek n) omdat deze bewerking de heap-eigenschap moet behouden (door heapify() aan te roepen) na het verwijderen van de root.
- invoegen() : Het plaatsen van een nieuwe sleutel duurt O(logboek n) tijd. We voegen een nieuwe sleutel toe aan het einde van de boom. Als de nieuwe sleutel kleiner is dan de bovenliggende sleutel, hoeven we niets te doen. Anders moeten we omhoog gaan om de geschonden heap-eigenschap te repareren.
Opmerking: In de onderstaande implementatie indexeren we vanaf index 1 om de implementatie te vereenvoudigen.
Python
scan.nextstring java
# Python3 implementation of Max Heap> import> sys> class> MaxHeap:> >def> __init__(>self>, maxsize):> > >self>.maxsize>=> maxsize> >self>.size>=> 0> >self>.Heap>=> [>0>]>*> (>self>.maxsize>+> 1>)> >self>.Heap[>0>]>=> sys.maxsize> >self>.FRONT>=> 1> ># Function to return the position of> ># parent for the node currently> ># at pos> >def> parent(>self>, pos):> > >return> pos>/>/> 2> ># Function to return the position of> ># the left child for the node currently> ># at pos> >def> leftChild(>self>, pos):> > >return> 2> *> pos> ># Function to return the position of> ># the right child for the node currently> ># at pos> >def> rightChild(>self>, pos):> > >return> (>2> *> pos)>+> 1> ># Function that returns true if the passed> ># node is a leaf node> >def> isLeaf(>self>, pos):> > >if> pos>>=> (>self>.size>/>/>2>)>and> pos <>=> self>.size:> >return> True> >return> False> ># Function to swap two nodes of the heap> >def> swap(>self>, fpos, spos):> > >self>.Heap[fpos],>self>.Heap[spos]>=> (>self>.Heap[spos],> >self>.Heap[fpos])> ># Function to heapify the node at pos> >def> maxHeapify(>self>, pos):> ># If the node is a non-leaf node and smaller> ># than any of its child> >if> not> self>.isLeaf(pos):> >if> (>self>.Heap[pos] <>self>.Heap[>self>.leftChild(pos)]>or> >self>.Heap[pos] <>self>.Heap[>self>.rightChild(pos)]):> ># Swap with the left child and heapify> ># the left child> >if> (>self>.Heap[>self>.leftChild(pos)]>> >self>.Heap[>self>.rightChild(pos)]):> >self>.swap(pos,>self>.leftChild(pos))> >self>.maxHeapify(>self>.leftChild(pos))> ># Swap with the right child and heapify> ># the right child> >else>:> >self>.swap(pos,>self>.rightChild(pos))> >self>.maxHeapify(>self>.rightChild(pos))> ># Function to insert a node into the heap> >def> insert(>self>, element):> > >if> self>.size>>=> self>.maxsize:> >return> >self>.size>+>=> 1> >self>.Heap[>self>.size]>=> element> >current>=> self>.size> >while> (>self>.Heap[current]>> >self>.Heap[>self>.parent(current)]):> >self>.swap(current,>self>.parent(current))> >current>=> self>.parent(current)> ># Function to print the contents of the heap> >def> Print>(>self>):> > >for> i>in> range>(>1>, (>self>.size>/>/> 2>)>+> 1>):> >print>(>'PARENT : '> +> str>(>self>.Heap[i])>+> >'LEFT CHILD : '> +> str>(>self>.Heap[>2> *> i])>+> >'RIGHT CHILD : '> +> str>(>self>.Heap[>2> *> i>+> 1>]))> ># Function to remove and return the maximum> ># element from the heap> >def> extractMax(>self>):> >popped>=> self>.Heap[>self>.FRONT]> >self>.Heap[>self>.FRONT]>=> self>.Heap[>self>.size]> >self>.size>->=> 1> >self>.maxHeapify(>self>.FRONT)> > >return> popped> # Driver Code> if> __name__>=>=> '__main__'>:> > >print>(>'The maxHeap is '>)> > >maxHeap>=> MaxHeap(>15>)> >maxHeap.insert(>5>)> >maxHeap.insert(>3>)> >maxHeap.insert(>17>)> >maxHeap.insert(>10>)> >maxHeap.insert(>84>)> >maxHeap.insert(>19>)> >maxHeap.insert(>6>)> >maxHeap.insert(>22>)> >maxHeap.insert(>9>)> >maxHeap.>Print>()> > >print>(>'The Max val is '> +> str>(maxHeap.extractMax()))> |
string naar booleaanse java
>
>Uitvoer
The maxHeap is PARENT : 84LEFT CHILD : 22RIGHT CHILD : 19 PARENT : 22LEFT CHILD : 17RIGHT CHILD : 10 PARENT : 19LEFT CHILD : 5RIGHT CHILD : 6 PARENT : 17LEFT CHILD : 3RIGHT CHILD : 9 The Max val is 84>
Bibliotheekfuncties gebruiken:
We gebruiken hoopq klasse om Heap in Python te implementeren. Standaard wordt Min Heap door deze klasse geïmplementeerd. Maar we vermenigvuldigen elke waarde met -1, zodat we deze als MaxHeap kunnen gebruiken.
Python3
linkse join versus rechtse join
# Python3 program to demonstrate working of heapq> from> heapq>import> heappop, heappush, heapify> # Creating empty heap> heap>=> []> heapify(heap)> # Adding items to the heap using heappush> # function by multiplying them with -1> heappush(heap,>->1> *> 10>)> heappush(heap,>->1> *> 30>)> heappush(heap,>->1> *> 20>)> heappush(heap,>->1> *> 400>)> # printing the value of maximum element> print>(>'Head value of heap : '> +> str>(>->1> *> heap[>0>]))> # printing the elements of the heap> print>(>'The heap elements : '>)> for> i>in> heap:> >print>((>->1>*>i), end>=>' '>)> print>(>'
'>)> element>=> heappop(heap)> # printing the elements of the heap> print>(>'The heap elements : '>)> for> i>in> heap:> >print>(>->1> *> i, end>=> ' '>)> |
>
vos versus wolf
>Uitvoer
Head value of heap : 400 The heap elements : 400 30 20 10 The heap elements : 30 10 20>
Bibliotheekfuncties gebruiken met de dunder-methode voor getallen, tekenreeksen, tupels, objecten enz
We gebruiken hoopq klasse om Heaps in Python te implementeren. Standaard wordt Min Heap door deze klasse geïmplementeerd.
Om MaxHeap te implementeren, niet beperkt tot alleen getallen, maar elk type object (String, Tuple, Object enz.), moeten we
- Maak een Wrapper-klasse voor het item in de lijst.
- Overschrijf de __lt__ dunder-methode om een omgekeerd resultaat te geven.
Hieronder volgt de implementatie van de hier genoemde methode.
'abc' is in cijfers'
Python3
'''> Python3 program to implement MaxHeap Operation> with built-in module heapq> for String, Numbers, Objects> '''> from> functools>import> total_ordering> import> heapq>|_+_| |