Binomiālās kaudzes ieviešana
In iepriekšējais raksts mēs esam apsprieduši jēdzienus, kas saistīti ar binomiālo kaudzi.
Binomiālās kaudzes piemēri:
12------------10--------------------20
/ / |
15 50 70 50 40
| / | |
30 80 85 65
|
100
A Binomial Heap with 13 nodes. It is a collection of 3
Binomial Trees of orders 0 2 and 3 from left to right.
10--------------------20
/ / |
15 50 70 50 40
| / | |
30 80 85 65
|
100Šajā rakstā ir apskatīta Binomial Heap ieviešana. Ieviestas šādas funkcijas:
- ievietot(H k): Ievieto atslēgu “k” binomiālajā kaudzē “H”. Šī darbība vispirms izveido binomiālo kaudzi ar vienu taustiņu “k”, pēc tam izsauc savienību H un jauno binomiālo kaudzi.
- getMin(H): Vienkāršs veids, kā iegūtMin(), ir šķērsot binomisko koku sakņu sarakstu un atgriezt minimālo atslēgu. Šai ieviešanai nepieciešams O(Logn) laiks. To var optimizēt uz O(1), saglabājot rādītāju uz minimālo atslēgas sakni.
- ekstraktsMin(H): Šī darbība izmanto arī union(). Vispirms mēs izsaucam getMin(), lai atrastu minimālo atslēgu Binomiālais koks, tad mēs noņemam mezglu un izveidojam jaunu Binomiālo kaudzi, savienojot visus noņemtā minimālā mezgla apakškokus. Visbeidzot mēs izsaucam union() uz H un jaunizveidoto Binomiālo kaudzi. Šai darbībai nepieciešams O (pieteikšanās) laiks.
Īstenošana:
CPPJava// C++ program to implement different operations // on Binomial Heap #includeusing namespace std ; // A Binomial Tree node. struct Node { int data degree ; Node * child * sibling * parent ; }; Node * newNode ( int key ) { Node * temp = new Node ; temp -> data = key ; temp -> degree = 0 ; temp -> child = temp -> parent = temp -> sibling = NULL ; return temp ; } // This function merge two Binomial Trees. Node * mergeBinomialTrees ( Node * b1 Node * b2 ) { // Make sure b1 is smaller if ( b1 -> data > b2 -> data ) swap ( b1 b2 ); // We basically make larger valued tree // a child of smaller valued tree b2 -> parent = b1 ; b2 -> sibling = b1 -> child ; b1 -> child = b2 ; b1 -> degree ++ ; return b1 ; } // This function perform union operation on two // binomial heap i.e. l1 & l2 list < Node *> unionBionomialHeap ( list < Node *> l1 list < Node *> l2 ) { // _new to another binomial heap which contain // new heap after merging l1 & l2 list < Node *> _new ; list < Node *>:: iterator it = l1 . begin (); list < Node *>:: iterator ot = l2 . begin (); while ( it != l1 . end () && ot != l2 . end ()) { // if D(l1) <= D(l2) if (( * it ) -> degree <= ( * ot ) -> degree ) { _new . push_back ( * it ); it ++ ; } // if D(l1) > D(l2) else { _new . push_back ( * ot ); ot ++ ; } } // if there remains some elements in l1 // binomial heap while ( it != l1 . end ()) { _new . push_back ( * it ); it ++ ; } // if there remains some elements in l2 // binomial heap while ( ot != l2 . end ()) { _new . push_back ( * ot ); ot ++ ; } return _new ; } // adjust function rearranges the heap so that // heap is in increasing order of degree and // no two binomial trees have same degree in this heap list < Node *> adjust ( list < Node *> _heap ) { if ( _heap . size () <= 1 ) return _heap ; list < Node *> new_heap ; list < Node *>:: iterator it1 it2 it3 ; it1 = it2 = it3 = _heap . begin (); if ( _heap . size () == 2 ) { it2 = it1 ; it2 ++ ; it3 = _heap . end (); } else { it2 ++ ; it3 = it2 ; it3 ++ ; } while ( it1 != _heap . end ()) { // if only one element remains to be processed if ( it2 == _heap . end ()) it1 ++ ; // If D(it1) < D(it2) i.e. merging of Binomial // Tree pointed by it1 & it2 is not possible // then move next in heap else if (( * it1 ) -> degree < ( * it2 ) -> degree ) { it1 ++ ; it2 ++ ; if ( it3 != _heap . end ()) it3 ++ ; } // if D(it1)D(it2) & D(it3) are same i.e. // degree of three consecutive Binomial Tree are same // in heap else if ( it3 != _heap . end () && ( * it1 ) -> degree == ( * it2 ) -> degree && ( * it1 ) -> degree == ( * it3 ) -> degree ) { it1 ++ ; it2 ++ ; it3 ++ ; } // if degree of two Binomial Tree are same in heap else if (( * it1 ) -> degree == ( * it2 ) -> degree ) { Node * temp ; * it1 = mergeBinomialTrees ( * it1 * it2 ); it2 = _heap . erase ( it2 ); if ( it3 != _heap . end ()) it3 ++ ; } } return _heap ; } // inserting a Binomial Tree into binomial heap list < Node *> insertATreeInHeap ( list < Node *> _heap Node * tree ) { // creating a new heap i.e temp list < Node *> temp ; // inserting Binomial Tree into heap temp . push_back ( tree ); // perform union operation to finally insert // Binomial Tree in original heap temp = unionBionomialHeap ( _heap temp ); return adjust ( temp ); } // removing minimum key element from binomial heap // this function take Binomial Tree as input and return // binomial heap after // removing head of that tree i.e. minimum element list < Node *> removeMinFromTreeReturnBHeap ( Node * tree ) { list < Node *> heap ; Node * temp = tree -> child ; Node * lo ; // making a binomial heap from Binomial Tree while ( temp ) { lo = temp ; temp = temp -> sibling ; lo -> sibling = NULL ; heap . push_front ( lo ); } return heap ; } // inserting a key into the binomial heap list < Node *> insert ( list < Node *> _head int key ) { Node * temp = newNode ( key ); return insertATreeInHeap ( _head temp ); } // return pointer of minimum value Node // present in the binomial heap Node * getMin ( list < Node *> _heap ) { list < Node *>:: iterator it = _heap . begin (); Node * temp = * it ; while ( it != _heap . end ()) { if (( * it ) -> data < temp -> data ) temp = * it ; it ++ ; } return temp ; } list < Node *> extractMin ( list < Node *> _heap ) { list < Node *> new_heap lo ; Node * temp ; // temp contains the pointer of minimum value // element in heap temp = getMin ( _heap ); list < Node *>:: iterator it ; it = _heap . begin (); while ( it != _heap . end ()) { if ( * it != temp ) { // inserting all Binomial Tree into new // binomial heap except the Binomial Tree // contains minimum element new_heap . push_back ( * it ); } it ++ ; } lo = removeMinFromTreeReturnBHeap ( temp ); new_heap = unionBionomialHeap ( new_heap lo ); new_heap = adjust ( new_heap ); return new_heap ; } // print function for Binomial Tree void printTree ( Node * h ) { while ( h ) { cout < < h -> data < < ' ' ; printTree ( h -> child ); h = h -> sibling ; } } // print function for binomial heap void printHeap ( list < Node *> _heap ) { list < Node *> :: iterator it ; it = _heap . begin (); while ( it != _heap . end ()) { printTree ( * it ); it ++ ; } } // Driver program to test above functions int main () { int ch key ; list < Node *> _heap ; // Insert data in the heap _heap = insert ( _heap 10 ); _heap = insert ( _heap 20 ); _heap = insert ( _heap 30 ); cout < < 'Heap elements after insertion: n ' ; printHeap ( _heap ); Node * temp = getMin ( _heap ); cout < < ' n Minimum element of heap ' < < temp -> data < < ' n ' ; // Delete minimum element of heap _heap = extractMin ( _heap ); cout < < 'Heap after deletion of minimum element n ' ; printHeap ( _heap ); return 0 ; } Python3// Java Program to Implement Binomial Heap // Importing required classes import java.io.* ; // Class 1 // BinomialHeapNode class BinomialHeapNode { int key degree ; BinomialHeapNode parent ; BinomialHeapNode sibling ; BinomialHeapNode child ; // Constructor of this class public BinomialHeapNode ( int k ) { key = k ; degree = 0 ; parent = null ; sibling = null ; child = null ; } // Method 1 // To reverse public BinomialHeapNode reverse ( BinomialHeapNode sibl ) { BinomialHeapNode ret ; if ( sibling != null ) ret = sibling . reverse ( this ); else ret = this ; sibling = sibl ; return ret ; } // Method 2 // To find minimum node public BinomialHeapNode findMinNode () { // this keyword refers to current instance itself BinomialHeapNode x = this y = this ; int min = x . key ; while ( x != null ) { if ( x . key < min ) { y = x ; min = x . key ; } x = x . sibling ; } return y ; } // Method 3 // To find node with key value public BinomialHeapNode findANodeWithKey ( int value ) { BinomialHeapNode temp = this node = null ; while ( temp != null ) { if ( temp . key == value ) { node = temp ; break ; } if ( temp . child == null ) temp = temp . sibling ; else { node = temp . child . findANodeWithKey ( value ); if ( node == null ) temp = temp . sibling ; else break ; } } return node ; } // Method 4 // To get the size public int getSize () { return ( 1 + (( child == null ) ? 0 : child . getSize ()) + (( sibling == null ) ? 0 : sibling . getSize ())); } } // Class 2 // BinomialHeap class BinomialHeap { // Member variables of this class private BinomialHeapNode Nodes ; private int size ; // Constructor of this class public BinomialHeap () { Nodes = null ; size = 0 ; } // Checking if heap is empty public boolean isEmpty () { return Nodes == null ; } // Method 1 // To get the size public int getSize () { return size ; } // Method 2 // Clear heap public void makeEmpty () { Nodes = null ; size = 0 ; } // Method 3 // To insert public void insert ( int value ) { if ( value > 0 ) { BinomialHeapNode temp = new BinomialHeapNode ( value ); if ( Nodes == null ) { Nodes = temp ; size = 1 ; } else { unionNodes ( temp ); size ++ ; } } } // Method 4 // To unite two binomial heaps private void merge ( BinomialHeapNode binHeap ) { BinomialHeapNode temp1 = Nodes temp2 = binHeap ; while (( temp1 != null ) && ( temp2 != null )) { if ( temp1 . degree == temp2 . degree ) { BinomialHeapNode tmp = temp2 ; temp2 = temp2 . sibling ; tmp . sibling = temp1 . sibling ; temp1 . sibling = tmp ; temp1 = tmp . sibling ; } else { if ( temp1 . degree < temp2 . degree ) { if (( temp1 . sibling == null ) || ( temp1 . sibling . degree > temp2 . degree )) { BinomialHeapNode tmp = temp2 ; temp2 = temp2 . sibling ; tmp . sibling = temp1 . sibling ; temp1 . sibling = tmp ; temp1 = tmp . sibling ; } else { temp1 = temp1 . sibling ; } } else { BinomialHeapNode tmp = temp1 ; temp1 = temp2 ; temp2 = temp2 . sibling ; temp1 . sibling = tmp ; if ( tmp == Nodes ) { Nodes = temp1 ; } else { } } } } if ( temp1 == null ) { temp1 = Nodes ; while ( temp1 . sibling != null ) { temp1 = temp1 . sibling ; } temp1 . sibling = temp2 ; } else { } } // Method 5 // For union of nodes private void unionNodes ( BinomialHeapNode binHeap ) { merge ( binHeap ); BinomialHeapNode prevTemp = null temp = Nodes nextTemp = Nodes . sibling ; while ( nextTemp != null ) { if (( temp . degree != nextTemp . degree ) || (( nextTemp . sibling != null ) && ( nextTemp . sibling . degree == temp . degree ))) { prevTemp = temp ; temp = nextTemp ; } else { if ( temp . key <= nextTemp . key ) { temp . sibling = nextTemp . sibling ; nextTemp . parent = temp ; nextTemp . sibling = temp . child ; temp . child = nextTemp ; temp . degree ++ ; } else { if ( prevTemp == null ) { Nodes = nextTemp ; } else { prevTemp . sibling = nextTemp ; } temp . parent = nextTemp ; temp . sibling = nextTemp . child ; nextTemp . child = temp ; nextTemp . degree ++ ; temp = nextTemp ; } } nextTemp = temp . sibling ; } } // Method 6 // To return minimum key public int findMinimum () { return Nodes . findMinNode (). key ; } // Method 7 // To delete a particular element */ public void delete ( int value ) { if (( Nodes != null ) && ( Nodes . findANodeWithKey ( value ) != null )) { decreaseKeyValue ( value findMinimum () - 1 ); extractMin (); } } // Method 8 // To decrease key with a given value */ public void decreaseKeyValue ( int old_value int new_value ) { BinomialHeapNode temp = Nodes . findANodeWithKey ( old_value ); if ( temp == null ) return ; temp . key = new_value ; BinomialHeapNode tempParent = temp . parent ; while (( tempParent != null ) && ( temp . key < tempParent . key )) { int z = temp . key ; temp . key = tempParent . key ; tempParent . key = z ; temp = tempParent ; tempParent = tempParent . parent ; } } // Method 9 // To extract the node with the minimum key public int extractMin () { if ( Nodes == null ) return - 1 ; BinomialHeapNode temp = Nodes prevTemp = null ; BinomialHeapNode minNode = Nodes . findMinNode (); while ( temp . key != minNode . key ) { prevTemp = temp ; temp = temp . sibling ; } if ( prevTemp == null ) { Nodes = temp . sibling ; } else { prevTemp . sibling = temp . sibling ; } temp = temp . child ; BinomialHeapNode fakeNode = temp ; while ( temp != null ) { temp . parent = null ; temp = temp . sibling ; } if (( Nodes == null ) && ( fakeNode == null )) { size = 0 ; } else { if (( Nodes == null ) && ( fakeNode != null )) { Nodes = fakeNode . reverse ( null ); size = Nodes . getSize (); } else { if (( Nodes != null ) && ( fakeNode == null )) { size = Nodes . getSize (); } else { unionNodes ( fakeNode . reverse ( null )); size = Nodes . getSize (); } } } return minNode . key ; } // Method 10 // To display heap public void displayHeap () { System . out . print ( 'nHeap : ' ); displayHeap ( Nodes ); System . out . println ( 'n' ); } private void displayHeap ( BinomialHeapNode r ) { if ( r != null ) { displayHeap ( r . child ); System . out . print ( r . key + ' ' ); displayHeap ( r . sibling ); } } } // Class 3 // Main class public class GFG { public static void main ( String [] args ) { // Make object of BinomialHeap BinomialHeap binHeap = new BinomialHeap (); // Inserting in the binomial heap // Custom input integer values binHeap . insert ( 12 ); binHeap . insert ( 8 ); binHeap . insert ( 5 ); binHeap . insert ( 15 ); binHeap . insert ( 7 ); binHeap . insert ( 2 ); binHeap . insert ( 9 ); // Size of binomial heap System . out . println ( 'Size of the binomial heap is ' + binHeap . getSize ()); // Displaying the binomial heap binHeap . displayHeap (); // Deletion in binomial heap binHeap . delete ( 15 ); binHeap . delete ( 8 ); // Size of binomial heap System . out . println ( 'Size of the binomial heap is ' + binHeap . getSize ()); // Displaying the binomial heap binHeap . displayHeap (); // Making the heap empty binHeap . makeEmpty (); // checking if heap is empty System . out . println ( binHeap . isEmpty ()); } }JavaScript''' Min Heap Implementation in Python ''' class MinHeap : def __init__ ( self ): ''' On this implementation the heap list is initialized with a value ''' self . heap_list = [ 0 ] self . current_size = 0 def sift_up ( self i ): ''' Moves the value up in the tree to maintain the heap property. ''' # While the element is not the root or the left element Stop = False while ( i // 2 > 0 ) and Stop == False : # If the element is less than its parent swap the elements if self . heap_list [ i ] < self . heap_list [ i // 2 ]: self . heap_list [ i ] self . heap_list [ i // 2 ] = self . heap_list [ i // 2 ] self . heap_list [ i ] else : Stop = True # Move the index to the parent to keep the properties i = i // 2 def insert ( self k ): ''' Inserts a value into the heap ''' # Append the element to the heap self . heap_list . append ( k ) # Increase the size of the heap. self . current_size += 1 # Move the element to its position from bottom to the top self . sift_up ( self . current_size ) def sift_down ( self i ): # if the current node has at least one child while ( i * 2 ) <= self . current_size : # Get the index of the min child of the current node mc = self . min_child ( i ) # Swap the values of the current element is greater than its min child if self . heap_list [ i ] > self . heap_list [ mc ]: self . heap_list [ i ] self . heap_list [ mc ] = self . heap_list [ mc ] self . heap_list [ i ] i = mc def min_child ( self i ): # If the current node has only one child return the index of the unique child if ( i * 2 ) + 1 > self . current_size : return i * 2 else : # Herein the current node has two children # Return the index of the min child according to their values if self . heap_list [ i * 2 ] < self . heap_list [( i * 2 ) + 1 ]: return i * 2 else : return ( i * 2 ) + 1 def delete_min ( self ): # Equal to 1 since the heap list was initialized with a value if len ( self . heap_list ) == 1 : return 'Empty heap' # Get root of the heap (The min value of the heap) root = self . heap_list [ 1 ] # Move the last value of the heap to the root self . heap_list [ 1 ] = self . heap_list [ self . current_size ] # Pop the last value since a copy was set on the root * self . heap_list _ = self . heap_list # Decrease the size of the heap self . current_size -= 1 # Move down the root (value at index 1) to keep the heap property self . sift_down ( 1 ) # Return the min value of the heap return root ''' Driver program ''' # Same tree as above example. my_heap = MinHeap () my_heap . insert ( 5 ) my_heap . insert ( 6 ) my_heap . insert ( 7 ) my_heap . insert ( 9 ) my_heap . insert ( 13 ) my_heap . insert ( 11 ) my_heap . insert ( 10 ) print ( my_heap . delete_min ()) # removing min node i.e 5
IzvadeHeap elements after insertion: 30 10 20 Minimum element of heap 10 Heap after deletion of minimum element 20 30Izveidojiet viktorīnu
![10 spēcīgākās valstis pasaulē pēc militārā spēka [2023]](https://techcodeview.com/img/current-gk/40/top-10-most-powerful-country-world-military-strength.webp)