EN Max-Heap er et komplet binært træ, hvor værdien i hver intern node er større end eller lig med værdierne i den pågældende nodes børn. At kortlægge elementerne i en heap til en matrix er trivielt: hvis en node er lagret et indeks k, så lagres dens venstre underordnede under indeks 2k+1 og dets rette barn ved indeks 2k+2 .
Eksempler på Max Heap:
Hvordan er Max Heap repræsenteret?
En maksimal bunke er et komplet binært træ. En max heap er typisk repræsenteret som en matrix. Rodelementet vil være ved Arr[0]. Nedenstående tabel viser indekser for andre noder for den ith node, dvs. Arr[i]:
- Arr[(i-1)/2] Returnerer den overordnede node.
- Arr[(2*i)+1] Returnerer den venstre underordnede node.
- Arr[(2*i)+2] Returnerer den rigtige underordnede node.
Operationer på Max Heap:
- getMax() : Det returnerer rodelementet af Max Heap. Tidskompleksiteten af denne operation er O(1) .
- extractMax() : Fjerner det maksimale element fra MaxHeap. Tidskompleksiteten af denne operation er O(log n) da denne operation skal vedligeholde heap-egenskaben (ved at kalde heapify()) efter at have fjernet roden.
- indsæt() : Indsættelse af en ny nøgle tager O(log n) tid. Vi tilføjer en ny nøgle for enden af træet. Hvis den nye nøgle er mindre end dens forælder, behøver vi ikke at gøre noget. Ellers er vi nødt til at krydse op for at reparere den krænkede bunkeejendom.
Bemærk: I nedenstående implementering foretager vi indeksering fra indeks 1 for at forenkle implementeringen.
Python
streng tilføje
# 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()))> |
>
heal tool gimp
>
rund matematik javaProduktion
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>
Brug af biblioteksfunktioner:
Vi bruger heapq klasse for at implementere Heap i Python. Min Heap er som standard implementeret af denne klasse. Men vi gange hver værdi med -1, så vi kan bruge den som MaxHeap.
Python3
uendelig løkke
# 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>=> ' '>)> |
>
>Produktion
Head value of heap : 400 The heap elements : 400 30 20 10 The heap elements : 30 10 20>
Brug af biblioteksfunktioner med dunder-metode til tal, strenge, tupler, objekter osv
Vi bruger heapq klasse for at implementere Heaps i Python. Min Heap er som standard implementeret af denne klasse.
For at implementere MaxHeap ikke begrænset til kun tal, men enhver type objekt (streng, tuple, objekt osv.) bør vi
- Opret en Wrapper-klasse for elementet på listen.
- Tilsidesæt __lt__ dunder metode til at give omvendt resultat.
Følgende er implementeringen af metoden nævnt her.
'abc' er i tal'
Python3
'''> Python3 program to implement MaxHeap Operation> with built-in module heapq> for String, Numbers, Objects> '''> from> functools>import> total_ordering> import> heapq>|_+_| |