A Min-Heap on täydellinen binääripuu, jossa kunkin sisäisen solmun arvo on pienempi tai yhtä suuri kuin kyseisen solmun lapsien arvot.
Keon elementtien yhdistäminen taulukkoon on triviaali: jos solmu on tallennettu indeksiin k , sitten se vasen lapsi on tallennettu hakemistoon 2k+1 ja se on oikea lapsi indeksissä 2k+2 varten 0-pohjainen indeksointi ja varten 1 perustuva indeksointi vasen lapsi on klo 2k ja oikea lapsi tulee olemaan 2k+1 .
Esimerkki Min Heapista:
5 13 / / 10 15 16 31 / / / 30 41 51 100 41>
Miten Min Heap on edustettuna?
Vähimmäiskeko on täydellinen binaaripuu. Vähimmäiskeko esitetään tyypillisesti taulukkona. Juurielementti on osoitteessa Arr[0] . Mille tahansa i:nnelle solmulle, ts. Arr[i] :
- Arr[(i -1) / 2] palauttaa pääsolmunsa. Arr[(2 * i) + 1] palauttaa vasemman alisolmun. Arr[(2 * i) + 2] palauttaa oikean alisolmun.
Toiminnot Min Heapissa:
- getMin() : Palauttaa Min-keon juurielementin. Aika Tämän toimenpiteen monimutkaisuus on O(1) . extractMin() : Poistaa minimielementin MinHeapista. Tämän operaation aika monimutkaisuus on O(Loki n) koska tämän toiminnon on säilytettävä keon ominaisuus (kutsumalla heapify()) rootin poistamisen jälkeen. insert() : Uuden avaimen lisääminen kestää O(Loki n) aika. Lisäämme uuden avaimen puun loppuun. Jos uusi avain on suurempi kuin sen yläavain, meidän ei tarvitse tehdä mitään. Muussa tapauksessa meidän täytyy kulkea ylös korjataksemme rikotun kasan ominaisuuden.
Alla on Min Heapin toteutus Pythonissa -
yleisyys javassa
Python 3
# Python3 implementation of Min Heap> > import> sys> > class> MinHeap:> > >def> __init__(>self>, maxsize):> >self>.maxsize>=> maxsize> >self>.size>=> 0> >self>.Heap>=> [>0>]>*>(>self>.maxsize>+> 1>)> >self>.Heap[>0>]>=> ->1> *> 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):> >return> pos>*>2> >>> > ># 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> minHeapify(>self>, pos):> > ># If the node is a non-leaf node and greater> ># than any of its child> >if> not> self>.isLeaf(pos):> >if> (>self>.Heap[pos]>>>self>.leftChild(pos)]>or> >self>.Heap[pos]>>>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>.minHeapify(>self>.leftChild(pos))> > ># Swap with the right child and heapify> ># the right child> >else>:> >self>.swap(pos,>self>.rightChild(pos))> >self>.minHeapify(>self>.rightChild(pos))> > ># Function to insert a node into the heap> >def> insert(>self>, element):> >if> self>.size>>>.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 build the min heap using> ># the minHeapify function> >def> minHeap(>self>):> > >for> pos>in> range>(>self>.size>/>/>2>,>0>,>->1>):> >self>.minHeapify(pos)> > ># Function to remove and return the minimum> ># element from the heap> >def> remove(>self>):> > >popped>=> self>.Heap[>self>.FRONT]> >self>.Heap[>self>.FRONT]>=> self>.Heap[>self>.size]> >self>.size>->=> 1> >self>.minHeapify(>self>.FRONT)> >return> popped> > # Driver Code> if> __name__>=>=> '__main__'>:> > >print>(>'The minHeap is '>)> >minHeap>=> MinHeap(>15>)> >minHeap.insert(>5>)> >minHeap.insert(>3>)> >minHeap.insert(>17>)> >minHeap.insert(>10>)> >minHeap.insert(>84>)> >minHeap.insert(>19>)> >minHeap.insert(>6>)> >minHeap.insert(>22>)> >minHeap.insert(>9>)> >minHeap.minHeap()> > >minHeap.>Print>()> >print>(>'The Min val is '> +> str>(minHeap.remove()))> |
dhl tarkoittaa mitä
>
>
Lähtö:
The Min Heap is PARENT : 3 LEFT CHILD : 5 RIGHT CHILD :6 PARENT : 5 LEFT CHILD : 9 RIGHT CHILD :84 PARENT : 6 LEFT CHILD : 19 RIGHT CHILD :17 PARENT : 9 LEFT CHILD : 22 RIGHT CHILD :10 The Min val is 3>
Kirjastotoimintojen käyttäminen:
Käytämme kasaq luokka toteuttaakseen Heapsin Pythonissa. Oletuksena tämä luokka toteuttaa Min Heapin.
javascript if -lause
Python 3
# Python3 program to demonstrate working of heapq> > from> heapq>import> heapify, heappush, heappop> > # Creating empty heap> heap>=> []> heapify(heap)> > # Adding items to the heap using heappush function> heappush(heap,>10>)> heappush(heap,>30>)> heappush(heap,>20>)> heappush(heap,>400>)> > # printing the value of minimum element> print>(>'Head value of heap : '>+>str>(heap[>0>]))> > # printing the elements of the heap> print>(>'The heap elements : '>)> for> i>in> heap:> >print>(i, end>=> ' '>)> print>(>'
'>)> > element>=> heappop(heap)> > # printing the elements of the heap> print>(>'The heap elements : '>)> for> i>in> heap:> >print>(i, end>=> ' '>)> |
java pari
>
>
Lähtö:
Head value of heap : 10 The heap elements : 10 30 20 400 The heap elements : 20 30 400>