logo

TechCodeview

Max Heap programmā Python

A Max-Heap ir pilnīgs binārs koks, kurā vērtība katrā iekšējā mezglā ir lielāka vai vienāda ar vērtībām šī mezgla atvasinātajos. Kaudzes elementu kartēšana masīvā ir triviāla: ja mezglam ir saglabāts indekss k, tad tā kreisais bērns tiek saglabāts indeksā. 2k+1 un tā labais bērns rādītājā 2k+2 .

Max Heap piemēri:



maksimālā kaudze

Kā tiek attēlots Max Heap?

Maksimālā kaudze ir pilnīgs binārais koks. Maksimālā kaudze parasti tiek attēlota kā masīvs. Saknes elements atradīsies Arr[0]. Zemāk tabulā ir parādīti citu i-tā mezgla mezglu indeksi, t.i., Arr[i]:

  • Arr[(i-1)/2] Atgriež vecāku mezglu.
  • Arr[(2*i)+1] Atgriež kreiso pakārtoto mezglu.
  • Arr[(2*i)+2] Atgriež pareizo pakārtoto mezglu.

Darbības ar Max Heap:

  1. getMax() : Tas atgriež Max Heap saknes elementu. Laiks Šīs operācijas sarežģītība ir O(1) .
  2. ekstraktsMax() : noņem maksimālo elementu no MaxHeap. Šīs operācijas laika sarežģītība ir O(log n) jo šai darbībai ir jāsaglabā kaudzes rekvizīts (izsaucot heapify()) pēc saknes noņemšanas.
  3. ievietot () : jaunas atslēgas ievietošana prasa O(log n) laiks. Mēs pievienojam jaunu atslēgu koka galā. Ja jaunā atslēga ir mazāka par tās vecāku, mums nekas nav jādara. Pretējā gadījumā mums ir jāpārvietojas augšup, lai labotu bojāto kaudzes īpašumu.

Piezīme: Tālāk sniegtajā ieviešanā mēs veicam indeksēšanu no 1. indeksi, lai vienkāršotu ieviešanu.



Python


datu bāzes dizains dbms





# 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()))>

binārā koka šķērsošana pēc kārtas 
>

>

Izvade 

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>

Izmantojot bibliotēkas funkcijas:

Mēs izmantojam kaudze q klasē, lai ieviestu kaudzi Python. Pēc noklusējuma šī klase ir ieviesusi Min Heap. Bet mēs reizinām katru vērtību ar -1, lai mēs to varētu izmantot kā MaxHeap.

Python3

atzvanīšanas ellē javascript




# 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>=> ' '>)>

shloka mehta 
>

>

Izvade 

Head value of heap : 400 The heap elements : 400 30 20 10 The heap elements : 30 10 20>

Bibliotēkas funkciju izmantošana ar dunder metodi skaitļiem, virknēm, virknēm, objektiem utt

Mēs izmantojam kaudze q klasē, lai ieviestu Heaps Python. Pēc noklusējuma šī klase ir ieviesusi Min Heap.

Lai ieviestu MaxHeap, neaprobežojoties tikai ar skaitļiem, bet ar jebkāda veida objektiem (virkni, kopu, objektu utt.), mums vajadzētu

  1. Izveidojiet Iesaiņojuma klasi saraksta vienumam.
  2. Ignorēt __lt__ dunder metodi, lai iegūtu apgrieztu rezultātu.

Tālāk ir aprakstīta šeit minētās metodes ieviešana.

"abc" ir skaitļos

Python3




'''> Python3 program to implement MaxHeap Operation> with built-in module heapq> for String, Numbers, Objects> '''> from> functools>import> total_ordering> import> heapq>|_+_|