Min Heap Pythonissa
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 -
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> >>> .Heap[> self> .leftChild(pos)]> or> > self> .Heap[pos]>>> 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 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()))> |
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.
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> => ' '> )> |
Lähtö:
Head value of heap : 10 The heap elements : 10 30 20 400 The heap elements : 20 30 400
