A Max-Heap és un arbre binari complet en el qual el valor de cada node intern és major o igual que els valors dels fills d'aquest node. Mapejar els elements d'un munt a una matriu és trivial: si un node s'emmagatzema un índex k, el seu fill esquerre s'emmagatzema a l'índex. 2k+1 i el seu fill dret a l'índex 2k+2 .
Exemples de Max Heap:
Com es representa Max Heap?
Un munt màxim és un arbre binari complet. Un munt màxim normalment es representa com una matriu. L'element arrel estarà a Arr[0]. La taula següent mostra índexs d'altres nodes per al node i, és a dir, Arr[i]:
- Arr[(i-1)/2] Retorna el node pare.
- Arr[(2*i)+1] Retorna el node fill esquerre.
- Arr[(2*i)+2] Retorna el node fill dret.
Operacions a Max Heap:
- getMax() : retorna l'element arrel de Max Heap. Temps La complexitat d'aquesta operació és O(1) .
- extractMax() : elimina l'element màxim de MaxHeap. La complexitat temporal d'aquesta operació és O(log n) ja que aquesta operació necessita mantenir la propietat heap (cridant a heapify()) després d'eliminar l'arrel.
- inserir () : inserció d'una nova clau pren O(log n) temps. Afegim una nova clau al final de l'arbre. Si la nova clau és més petita que la seva pare, no hem de fer res. En cas contrari, haurem de recórrer cap amunt per arreglar la propietat del munt violada.
Nota: A la implementació següent, fem una indexació des de l'índex 1 per simplificar la implementació.
Python
administrador de powershell
iterador de mapes 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()))> |
>
>Sortida
java booleà
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>
Ús de les funcions de la biblioteca:
Fem servir heapq classe per implementar Heap a Python. Per defecte, aquesta classe implementa Min Heap. Però multipliquem cada valor per -1 perquè puguem utilitzar-lo com a MaxHeap.
Python 3
# 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>=> ' '>)> |
>
com eliminar el primer caràcter en excel
>Sortida
Head value of heap : 400 The heap elements : 400 30 20 10 The heap elements : 30 10 20>
Ús de funcions de biblioteca amb el mètode dunder per a números, cadenes, tuples, objectes, etc
Fem servir heapq classe per implementar Heaps en Python. Per defecte, aquesta classe implementa Min Heap.
Per implementar MaxHeap no limitant-se només als números sinó a qualsevol tipus d'objecte (String, Tuple, Object, etc.) hauríem de
- Creeu una classe Wrapper per a l'element de la llista.
- Anul·lar el __lt__ mètode dunder per donar un resultat invers.
A continuació es mostra la implementació del mètode esmentat aquí.
java tostring
Python 3
'''> Python3 program to implement MaxHeap Operation> with built-in module heapq> for String, Numbers, Objects> '''> from> functools>import> total_ordering> import> heapq>|_+_| |