Implementazione dell'heap binomiale
In articolo precedente abbiamo discusso dei concetti relativi all'heap binomiale.
Esempi di heap binomiale:
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
|
100In questo articolo viene discussa l'implementazione di Binomial Heap. Implementate le seguenti funzioni:
- inserire(Hk): Inserisce una chiave "k" nell'heap binomiale "H". Questa operazione crea innanzitutto un heap binomiale con la singola chiave "k", quindi richiama l'unione su H e il nuovo heap binomiale.
- getMin(H): Un modo semplice per getMin() è attraversare l'elenco delle radici degli alberi binomiali e restituire la chiave minima. Questa implementazione richiede tempo O(Logn). Può essere ottimizzato su O(1) mantenendo un puntatore alla radice della chiave minima.
- estrattoMin(H): Anche questa operazione utilizza union(). Per prima cosa chiamiamo getMin() per trovare l'albero binomiale con chiave minima, quindi rimuoviamo il nodo e creiamo un nuovo heap binomiale collegando tutti i sottoalberi del nodo minimo rimosso. Infine chiamiamo union() su H e il Binomial Heap appena creato. Questa operazione richiede tempo O(Logn).
Attuazione:
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
ProduzioneHeap elements after insertion: 30 10 20 Minimum element of heap 10 Heap after deletion of minimum element 20 30Crea quiz
