Min Heap w Pythonie
A Min-Sterta to kompletne drzewo binarne, w którym wartość w każdym węźle wewnętrznym jest mniejsza lub równa wartościom w elementach potomnych tego węzła.
Mapowanie elementów sterty na tablicę jest proste: jeśli węzeł jest przechowywany w indeksie k , to jest pozostawione dziecko jest przechowywany w indeksie 2k+1 i jego właściwe dziecko w indeksie 2k+2 Do Indeksowanie oparte na 0 i dla 1 indeksowanie oparte lewe dziecko będzie w 2 tys i właściwe dziecko będzie 2k+1 .
Przykład minimalnej sterty:
5 13 / / 10 15 16 31 / / / 30 41 51 100 41
Jak jest reprezentowany Min Heap?
Min Heap to kompletne drzewo binarne. Kopiec Min jest zwykle reprezentowany jako tablica. Element główny będzie w Arr[0] . Dla dowolnego i-tego węzła, tj. Arr[i] :
- Arr[(i -1) / 2] zwraca węzeł nadrzędny. Arr[(2 * i) + 1] zwraca lewy węzeł podrzędny. Arr[(2 * i) + 2] zwraca prawy węzeł podrzędny.
Operacje na Min Heap:
- getMin(): Zwraca element główny sterty Min. Złożoność czasowa tej operacji wynosi O(1) . ekstraktMin() : Usuwa minimalny element z MinHeap. Złożoność czasowa tej operacji wynosi O(Log n) ponieważ ta operacja wymaga zachowania właściwości sterty (poprzez wywołanie funkcji heapify()) po usunięciu roota. wstaw(): Wstawienie nowego klucza trwa O(Log n) czas. Dodajemy nowy klucz na końcu drzewa. Jeśli nowy klucz jest większy niż jego rodzic, nie musimy nic robić. W przeciwnym razie musimy przejść w górę, aby naprawić naruszoną właściwość sterty.
Poniżej znajduje się implementacja Min Heap w Pythonie –
Python3
# 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> >> self> .size> > > # 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> .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> .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>> => 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()))> |
Wyjście :
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
Korzystanie z funkcji biblioteki:
Używamy sterta class do implementacji stert w Pythonie. Domyślnie ta klasa implementuje Min Heap.
Python3
# 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> => ' '> )> |
Wyjście :
Head value of heap : 10 The heap elements : 10 30 20 400 The heap elements : 20 30 400
