Implement the insert and delete functions on Priority queue without Array
A priority Queue is a type of queue in which every element is associated with a priority and is served according to its priority.
We will use two popular data structures for implementing priority queues without arrays –
- Fibonacci Heap
- Binomial Heap
Fibonacci Heap:
Fibonacci heap is a heap data structure that is composed of a collection of min-heap-ordered trees. It has a faster-amortized running time than many other priority queue data structures including the binary heap and binomial heap.
- Insertion in Fibonacci Heap: Insertion in a Fibonacci heap is done by creating a new tree with the key of the inserted element and making it a child of the root list. The tree is then linked to the root list.
- Deletion in Fibonacci Heap: Deletion in a Fibonacci heap is done by first removing the element to be deleted from the root list and then merging the children of the deleted element into the root list. The resulting heap is then consolidated by repeatedly merging roots of the same degree.
Following are the program to demonstrate Insertion() and Deletion() operations on a Fibonacci Heap:
C++
// C++ program to demonstrate Extract // min, Deletion() and Decrease key() // operations in a fibonacci heap #include <cmath> #include <cstdlib> #include <iostream> #include <malloc.h> using namespace std; // Creating a structure to represent a // node in the heap struct node { // Parent pointer node* parent; // Child pointer node* child; // Pointer to the node on the left node* left; // Pointer to the node on the right node* right; // Value of the node int key; // Degree of the node int degree; // Black or white mark of the node char mark; // Flag for assisting in the Find // node function char c; }; // Creating min pointer as "mini" struct node* mini = NULL; // Declare an integer for number of // nodes in the heap int no_of_nodes = 0; // Function to insert a node in heap void insertion( int val) { struct node* new_node = new node(); new_node->key = val; new_node->degree = 0; new_node->mark = 'W' ; new_node->c = 'N' ; new_node->parent = NULL; new_node->child = NULL; new_node->left = new_node; new_node->right = new_node; if (mini != NULL) { (mini->left)->right = new_node; new_node->right = mini; new_node->left = mini->left; mini->left = new_node; if (new_node->key < mini->key) mini = new_node; } else { mini = new_node; } no_of_nodes++; } // Linking the heap nodes in parent // child relationship void Fibonnaci_link( struct node* ptr2, struct node* ptr1) { (ptr2->left)->right = ptr2->right; (ptr2->right)->left = ptr2->left; if (ptr1->right == ptr1) mini = ptr1; ptr2->left = ptr2; ptr2->right = ptr2; ptr2->parent = ptr1; if (ptr1->child == NULL) ptr1->child = ptr2; ptr2->right = ptr1->child; ptr2->left = (ptr1->child)->left; ((ptr1->child)->left)->right = ptr2; (ptr1->child)->left = ptr2; if (ptr2->key < (ptr1->child)->key) ptr1->child = ptr2; ptr1->degree++; } // Consolidating the heap void Consolidate() { int temp1; float temp2 = ( log (no_of_nodes)) / ( log (2)); int temp3 = temp2; struct node* arr[temp3 + 1]; for ( int i = 0; i <= temp3; i++) arr[i] = NULL; node* ptr1 = mini; node* ptr2; node* ptr3; node* ptr4 = ptr1; do { ptr4 = ptr4->right; temp1 = ptr1->degree; while (arr[temp1] != NULL) { ptr2 = arr[temp1]; if (ptr1->key > ptr2->key) { ptr3 = ptr1; ptr1 = ptr2; ptr2 = ptr3; } if (ptr2 == mini) mini = ptr1; Fibonnaci_link(ptr2, ptr1); if (ptr1->right == ptr1) mini = ptr1; arr[temp1] = NULL; temp1++; } arr[temp1] = ptr1; ptr1 = ptr1->right; } while (ptr1 != mini); mini = NULL; for ( int j = 0; j <= temp3; j++) { if (arr[j] != NULL) { arr[j]->left = arr[j]; arr[j]->right = arr[j]; if (mini != NULL) { (mini->left)->right = arr[j]; arr[j]->right = mini; arr[j]->left = mini->left; mini->left = arr[j]; if (arr[j]->key < mini->key) mini = arr[j]; } else { mini = arr[j]; } if (mini == NULL) mini = arr[j]; else if (arr[j]->key < mini->key) mini = arr[j]; } } } // Function to extract minimum node // in the heap void Extract_min() { if (mini == NULL) cout << "The heap is empty" << endl; else { node* temp = mini; node* pntr; pntr = temp; node* x = NULL; if (temp->child != NULL) { x = temp->child; do { pntr = x->right; (mini->left)->right = x; x->right = mini; x->left = mini->left; mini->left = x; if (x->key < mini->key) mini = x; x->parent = NULL; x = pntr; } while (pntr != temp->child); } (temp->left)->right = temp->right; (temp->right)->left = temp->left; mini = temp->right; if (temp == temp->right && temp->child == NULL) mini = NULL; else { mini = temp->right; Consolidate(); } no_of_nodes--; } } // Cutting a node in the heap to be placed // in the root list void Cut( struct node* found, struct node* temp) { if (found == found->right) temp->child = NULL; (found->left)->right = found->right; (found->right)->left = found->left; if (found == temp->child) temp->child = found->right; temp->degree = temp->degree - 1; found->right = found; found->left = found; (mini->left)->right = found; found->right = mini; found->left = mini->left; mini->left = found; found->parent = NULL; found->mark = 'B' ; } // Recursive cascade cutting function void Cascase_cut( struct node* temp) { node* ptr5 = temp->parent; if (ptr5 != NULL) { if (temp->mark == 'W' ) { temp->mark = 'B' ; } else { Cut(temp, ptr5); Cascase_cut(ptr5); } } } // Function to decrease the value of // a node in the heap void Decrease_key( struct node* found, int val) { if (mini == NULL) cout << "The Heap is Empty" << endl; if (found == NULL) cout << "Node not found in the Heap" << endl; found->key = val; struct node* temp = found->parent; if (temp != NULL && found->key < temp->key) { Cut(found, temp); Cascase_cut(temp); } if (found->key < mini->key) mini = found; } // Function to find the given node void Find( struct node* mini, int old_val, int val) { struct node* found = NULL; node* temp5 = mini; temp5->c = 'Y' ; node* found_ptr = NULL; if (temp5->key == old_val) { found_ptr = temp5; temp5->c = 'N' ; found = found_ptr; Decrease_key(found, val); } if (found_ptr == NULL) { if (temp5->child != NULL) Find(temp5->child, old_val, val); if ((temp5->right)->c != 'Y' ) Find(temp5->right, old_val, val); } temp5->c = 'N' ; found = found_ptr; } // Deleting a node from the heap void Deletion( int val) { if (mini == NULL) cout << "The heap is empty" << endl; else { // Decreasing the value of the // node to 0 Find(mini, val, 0); // Calling Extract_min function to // delete minimum value node, // which is 0 Extract_min(); cout << "Key Deleted" << endl; } } // Function to display the heap void display() { node* ptr = mini; if (ptr == NULL) cout << "The Heap is Empty" << endl; else { cout << "The root nodes of Heap are: " << endl; do { cout << ptr->key; ptr = ptr->right; if (ptr != mini) { cout << "-->" ; } } while (ptr != mini && ptr->right != NULL); cout << endl << "The heap has " << no_of_nodes << " node" << endl << endl; } } // Driver code int main() { // We will create a heap and insert // 3 nodes into it cout << "Creating an initial heap" << endl; insertion(5); insertion(2); insertion(8); // Now we will display the root list // of the heap display(); // Now we will delete the node '7' cout << "Delete the node 8" << endl; Deletion(8); cout << "Delete the node 5" << endl; Deletion(5); display(); return 0; } |
Java
// Java program to demonstrate Extract // min, Deletion() and Decrease key() // operations in a fibonacci heap import java.util.*; // Creating a structure to represent a // node in the heap class Node { // Parent pointer Node parent; // Child pointer Node child; // Pointer to the node on the left Node left; // Pointer to the node on the right Node right; // Value of the node int key; // Degree of the node int degree; // Black or white mark of the node char mark; // Flag for assisting in the Find // node function char c; } class GFG { // Creating min pointer as "mini" static Node mini = null ; // Declare an integer for number of // nodes in the heap static int no_of_nodes = 0 ; // Function to insert a node in heap static void insertion( int val) { Node new_node = new Node(); new_node.key = val; new_node.degree = 0 ; new_node.mark = 'W' ; new_node.c = 'N' ; new_node.parent = null ; new_node.child = null ; new_node.left = new_node; new_node.right = new_node; if (mini != null ) { mini.left.right = new_node; new_node.right = mini; new_node.left = mini.left; mini.left = new_node; if (new_node.key < mini.key) mini = new_node; } else { mini = new_node; } no_of_nodes++; } // Linking the heap nodes in parent // child relationship static void Fibonnaci_link(Node ptr2, Node ptr1) { ptr2.left.right = ptr2.right; ptr2.right.left = ptr2.left; if (ptr1.right == ptr1) { mini = ptr1; } ptr2.left = ptr2; ptr2.right = ptr2; ptr2.parent = ptr1; if (ptr1.child == null ) { ptr1.child = ptr2; } ptr2.right = ptr1.child; ptr2.left = ptr1.child.left; ptr1.child.left.right = ptr2; ptr1.child.left = ptr2; if (ptr2.key < ptr1.child.key) { ptr1.child = ptr2; } ptr1.degree++; } // Consolidating the heap static void Consolidate() { int temp1; double temp2 = (Math.log(no_of_nodes)) / (Math.log( 2 )); int temp3 = ( int )temp2; Node[] arr = new Node[temp3 + 1 ]; for ( int i = 0 ; i <= temp3; i++) { arr[i] = null ; } Node ptr1 = mini; Node ptr2; Node ptr3; Node ptr4 = ptr1; do { ptr4 = ptr4.right; temp1 = ptr1.degree; while (arr[temp1] != null ) { ptr2 = arr[temp1]; if (ptr1.key > ptr2.key) { ptr3 = ptr1; ptr1 = ptr2; ptr2 = ptr3; } if (ptr2 == mini) { mini = ptr1; } Fibonnaci_link(ptr2, ptr1); if (ptr1.right == ptr1) { mini = ptr1; } arr[temp1] = null ; temp1++; } arr[temp1] = ptr1; ptr1 = ptr1.right; } while (ptr1 != mini); mini = null ; for ( int j = 0 ; j <= temp3; j++) { if (arr[j] != null ) { arr[j].left = arr[j]; arr[j].right = arr[j]; if (mini != null ) { mini.left.right = arr[j]; arr[j].right = mini; arr[j].left = mini.left; mini.left = arr[j]; if (arr[j].key < mini.key) { mini = arr[j]; } } else { mini = arr[j]; } if (mini == null ) mini = arr[j]; else if (arr[j].key < mini.key) mini = arr[j]; } } } // Function to extract minimum node // in the heap static void Extract_min() { if (mini == null ) { System.out.println( "The heap is empty" ); } else { Node temp = mini; Node pntr; pntr = temp; Node x = null ; if (temp.child != null ) { x = temp.child; do { pntr = x.right; mini.left.right = x; x.right = mini; x.left = mini.left; mini.left = x; if (x.key < mini.key) { mini = x; } x.parent = null ; x = pntr; } while (pntr != temp.child); } temp.left.right = temp.right; temp.right.left = temp.left; mini = temp.right; if (temp == temp.right && temp.child == null ) { mini = null ; } else { mini = temp.right; Consolidate(); } no_of_nodes--; } } // Cutting a node in the heap to be placed // in the root list static void Cut(Node found, Node temp) { if (found == found.right) { temp.child = null ; } found.left.right = found.right; found.right.left = found.left; if (found == temp.child) { temp.child = found.right; } temp.degree--; found.right = found; found.left = found; mini.left.right = found; found.right = mini; found.left = mini.left; mini.left = found; found.parent = null ; found.mark = 'B' ; } // Recursive cascade cutting function static void Cascase_cut(Node temp) { Node ptr5 = temp.parent; if (ptr5 != null ) { if (temp.mark == 'W' ) { temp.mark = 'B' ; } else { Cut(temp, ptr5); Cascase_cut(ptr5); } } } // Function to decrease the value of // a node in the heap static void Decrease_key(Node found, int val) { if (mini == null ) { System.out.println( "The Heap is Empty" ); } if (found == null ) { System.out.println( "Node not found in the Heap" ); } found.key = val; Node temp = found.parent; if (temp != null && found.key < temp.key) { Cut(found, temp); Cascase_cut(temp); } if (found.key < mini.key) { mini = found; } } // Function to find the given node static void Find(Node mini, int old_val, int val) { Node found = null ; Node temp5 = mini; temp5.c = 'Y' ; Node foundPtr = null ; if (temp5.key == old_val) { foundPtr = temp5; temp5.c = 'N' ; found = foundPtr; Decrease_key(found, val); } if (foundPtr == null ) { if (temp5.child != null ) { Find(temp5.child, old_val, val); } if ((temp5.right).c != 'Y' ) { Find(temp5.right, old_val, val); } } temp5.c = 'N' ; found = foundPtr; } // Deleting a node from the heap static void Deletion( int val) { if (mini == null ) { System.out.println( "The heap is empty" ); } else { // Decreasing the value of the // node to 0 Find(mini, val, 0 ); // Calling Extract_min function to // delete minimum value node, // which is 0 Extract_min(); System.out.println( "Key Deleted" ); } } // Function to display the heap static void display() { Node ptr = mini; if (ptr == null ) { System.out.println( "The Heap is Empty" ); } else { System.out.println( "The root nodes of Heap are: " ); do { System.out.print(ptr.key); ptr = ptr.right; if (ptr != mini) { System.out.print( "-->" ); } } while (ptr != mini && ptr.right != null ); System.out.println(); System.out.println( "The heap has " + no_of_nodes + " node" ); System.out.println(); } } // Driver code public static void main(String[] args) { // We will create a heap and insert // 3 nodes into it System.out.println( "Creating an initial heap" ); insertion( 5 ); insertion( 2 ); insertion( 8 ); // Now we will display the root list // of the heap display(); // Now we will delete the node '7' System.out.println( "Delete the node 8" ); Deletion( 8 ); System.out.println( "Delete the node 5" ); Deletion( 5 ); display(); } } // This Code is Contributed by Prasad Kandekar(prasad264) |
Python3
import math class Node: def __init__( self , key): self .parent = None self .child = None self .left = None self .right = None self .key = key self .degree = 0 self .mark = 'W' # White mark indicates unmarked self .c = 'N' # Flag for assisting in the Find node function # Creating min pointer as "mini" mini = None # Declare an integer for the number of nodes in the heap no_of_nodes = 0 # Function to insert a node in the heap def insertion(val): global mini, no_of_nodes new_node = Node(val) new_node.degree = 0 new_node.mark = 'W' new_node.c = 'N' new_node.parent = None new_node.child = None new_node.left = new_node new_node.right = new_node if mini is not None : mini.left.right = new_node new_node.right = mini new_node.left = mini.left mini.left = new_node if new_node.key < mini.key: mini = new_node else : mini = new_node no_of_nodes + = 1 # Linking the heap nodes in a parent-child relationship def fibonnaci_link(ptr2, ptr1): ptr2.left.right = ptr2.right ptr2.right.left = ptr2.left if ptr1.right = = ptr1: global mini mini = ptr1 ptr2.left = ptr2 ptr2.right = ptr2 ptr2.parent = ptr1 if ptr1.child is None : ptr1.child = ptr2 ptr2.right = ptr1.child ptr2.left = ptr1.child.left ptr1.child.left.right = ptr2 ptr1.child.left = ptr2 if ptr2.key < ptr1.child.key: ptr1.child = ptr2 ptr1.degree + = 1 # Consolidating the heap def consolidate(): global mini, no_of_nodes temp2 = math.log(no_of_nodes) / math.log( 2 ) temp3 = int (temp2) arr = [ None ] * (temp3 + 1 ) ptr1 = mini ptr2 = None ptr3 = None ptr4 = ptr1 while True : ptr4 = ptr4.right temp1 = ptr1.degree while arr[temp1] is not None : ptr2 = arr[temp1] if ptr1.key > ptr2.key: ptr3 = ptr1 ptr1 = ptr2 ptr2 = ptr3 if ptr2 = = mini: mini = ptr1 fibonnaci_link(ptr2, ptr1) if ptr1.right = = ptr1: mini = ptr1 arr[temp1] = None temp1 + = 1 arr[temp1] = ptr1 ptr1 = ptr1.right if ptr1 = = mini: break mini = None for j in range (temp3 + 1 ): if arr[j] is not None : arr[j].left = arr[j] arr[j].right = arr[j] if mini is not None : mini.left.right = arr[j] arr[j].right = mini arr[j].left = mini.left mini.left = arr[j] if arr[j].key < mini.key: mini = arr[j] else : mini = arr[j] if mini is None : mini = arr[j] elif arr[j].key < mini.key: mini = arr[j] # Function to extract the minimum node in the heap def extract_min(): global mini, no_of_nodes if mini is None : print ( "The heap is empty" ) else : temp = mini pntr = temp x = None if temp.child is not None : x = temp.child while True : pntr = x.right mini.left.right = x x.right = mini x.left = mini.left mini.left = x if x.key < mini.key: mini = x x.parent = None x = pntr if pntr = = temp.child: break temp.left.right = temp.right temp.right.left = temp.left mini = temp.right if temp = = temp.right and temp.child is None : mini = None else : mini = temp.right consolidate() no_of_nodes - = 1 # Cutting a node in the heap to be placed in the root list def cut(found, temp): global mini if found = = found.right: temp.child = None found.left.right = found.right found.right.left = found.left if found = = temp.child: temp.child = found.right temp.degree = temp.degree - 1 found.right = found found.left = found mini.left.right = found found.right = mini found.left = mini.left mini.left = found found.parent = None found.mark = 'B' # Recursive cascade cutting function def cascade_cut(temp): global mini ptr5 = temp.parent if ptr5 is not None : if temp.mark = = 'W' : temp.mark = 'B' else : cut(temp, ptr5) cascade_cut(ptr5) # Function to decrease the value of a node in the heap def decrease_key(found, val): global mini if mini is None : print ( "The Heap is Empty" ) if found is None : print ( "Node not found in the Heap" ) found.key = val temp = found.parent if temp is not None and found.key < temp.key: cut(found, temp) cascade_cut(temp) if found.key < mini.key: mini = found # Function to find the given node def find(mini, old_val, val): # mini found = None temp5 = mini temp5.c = 'Y' found_ptr = None if temp5.key = = old_val: found_ptr = temp5 temp5.c = 'N' found = found_ptr decrease_key(found, val) if found_ptr is None : if temp5.child is not None : find(temp5.child, old_val, val) if temp5.right.c ! = 'Y' : find(temp5.right, old_val, val) temp5.c = 'N' found = found_ptr # Deleting a node from the heap def deletion(val): global mini if mini is None : print ( "The heap is empty" ) else : # Decreasing the value of the node to 0 find(mini, val, 0 ) # Calling Extract_min function to delete the minimum value node, which is 0 extract_min() print ( "Key Deleted" ) # Function to display the heap def display(): global mini, no_of_nodes ptr = mini if ptr is None : print ( "The Heap is Empty" ) else : print ( "The root nodes of Heap are:" ) while True : print (ptr.key, end = "") ptr = ptr.right if ptr ! = mini: print ( "-->" , end = " " ) if ptr = = mini: break print ( "\nThe heap has" , no_of_nodes, "node(s)\n" ) # Driver code if __name__ = = "__main__" : # We will create a heap and insert 3 nodes into it print ( "Creating an initial heap" ) insertion( 5 ) insertion( 2 ) insertion( 8 ) # Now we will display the root list of the heap display() # Now we will delete the node '8' print ( "Delete the node 8" ) deletion( 8 ) # display() # Now we will delete the node '5' print ( "Delete the node 5" ) deletion( 5 ) display() |
C#
// C# program to demonstrate Extract // min, Deletion() and Decrease key() // operations in a fibonacci heap using System; // Creating a structure to represent a // node in the heap class Node { // Parent pointer public Node parent; // Child pointer public Node child; // Pointer to the node on the left public Node left; // Pointer to the node on the right public Node right; // Value of the node public int key; // Degree of the node public int degree; // Black or white mark of the node public char mark; // Flag for assisting in the Find // node function public char c; } class GFG { // Creating min pointer as "mini" static Node mini = null ; // Declare an integer for number of // nodes in the heap static int no_of_nodes = 0; // Function to insert a node in heap static void insertion( int val) { Node new_node = new Node(); new_node.key = val; new_node.degree = 0; new_node.mark = 'W' ; new_node.c = 'N' ; new_node.parent = null ; new_node.child = null ; new_node.left = new_node; new_node.right = new_node; if (mini != null ) { mini.left.right = new_node; new_node.right = mini; new_node.left = mini.left; mini.left = new_node; if (new_node.key < mini.key) mini = new_node; } else { mini = new_node; } no_of_nodes++; } // Linking the heap nodes in parent // child relationship static void Fibonnaci_link(Node ptr2, Node ptr1) { ptr2.left.right = ptr2.right; ptr2.right.left = ptr2.left; if (ptr1.right == ptr1) { mini = ptr1; } ptr2.left = ptr2; ptr2.right = ptr2; ptr2.parent = ptr1; if (ptr1.child == null ) { ptr1.child = ptr2; } ptr2.right = ptr1.child; ptr2.left = ptr1.child.left; ptr1.child.left.right = ptr2; ptr1.child.left = ptr2; if (ptr2.key < ptr1.child.key) { ptr1.child = ptr2; } ptr1.degree++; } // Consolidating the heap static void Consolidate() { int temp1; double temp2 = (Math.Log(no_of_nodes)) / (Math.Log(2)); int temp3 = ( int )temp2; Node[] arr = new Node[temp3 + 1]; for ( int i = 0; i <= temp3; i++) { arr[i] = null ; } Node ptr1 = mini; Node ptr2; Node ptr3; Node ptr4 = ptr1; do { ptr4 = ptr4.right; temp1 = ptr1.degree; while (arr[temp1] != null ) { ptr2 = arr[temp1]; if (ptr1.key > ptr2.key) { ptr3 = ptr1; ptr1 = ptr2; ptr2 = ptr3; } if (ptr2 == mini) { mini = ptr1; } Fibonnaci_link(ptr2, ptr1); if (ptr1.right == ptr1) { mini = ptr1; } arr[temp1] = null ; temp1++; } arr[temp1] = ptr1; ptr1 = ptr1.right; } while (ptr1 != mini); mini = null ; for ( int j = 0; j <= temp3; j++) { if (arr[j] != null ) { arr[j].left = arr[j]; arr[j].right = arr[j]; if (mini != null ) { mini.left.right = arr[j]; arr[j].right = mini; arr[j].left = mini.left; mini.left = arr[j]; if (arr[j].key < mini.key) { mini = arr[j]; } } else { mini = arr[j]; } if (mini == null ) mini = arr[j]; else if (arr[j].key < mini.key) mini = arr[j]; } } } // Function to extract minimum node // in the heap static void Extract_min() { if (mini == null ) { Console.WriteLine( "The heap is empty" ); } else { Node temp = mini; Node pntr; pntr = temp; Node x = null ; if (temp.child != null ) { x = temp.child; do { pntr = x.right; mini.left.right = x; x.right = mini; x.left = mini.left; mini.left = x; if (x.key < mini.key) { mini = x; } x.parent = null ; x = pntr; } while (pntr != temp.child); } temp.left.right = temp.right; temp.right.left = temp.left; mini = temp.right; if (temp == temp.right && temp.child == null ) { mini = null ; } else { mini = temp.right; Consolidate(); } no_of_nodes--; } } // Cutting a node in the heap to be placed // in the root list static void Cut(Node found, Node temp) { if (found == found.right) { temp.child = null ; } found.left.right = found.right; found.right.left = found.left; if (found == temp.child) { temp.child = found.right; } temp.degree--; found.right = found; found.left = found; mini.left.right = found; found.right = mini; found.left = mini.left; mini.left = found; found.parent = null ; found.mark = 'B' ; } // Recursive cascade cutting function static void Cascase_cut(Node temp) { Node ptr5 = temp.parent; if (ptr5 != null ) { if (temp.mark == 'W' ) { temp.mark = 'B' ; } else { Cut(temp, ptr5); Cascase_cut(ptr5); } } } // Function to decrease the value of // a node in the heap static void Decrease_key(Node found, int val) { if (mini == null ) { Console.WriteLine( "The Heap is Empty" ); } if (found == null ) { Console.WriteLine( "Node not found in the Heap" ); } found.key = val; Node temp = found.parent; if (temp != null && found.key < temp.key) { Cut(found, temp); Cascase_cut(temp); } if (found.key < mini.key) { mini = found; } } // Function to find the given node static void Find(Node mini, int old_val, int val) { Node found = null ; Node temp5 = mini; temp5.c = 'Y' ; Node foundPtr = null ; if (temp5.key == old_val) { foundPtr = temp5; temp5.c = 'N' ; found = foundPtr; Decrease_key(found, val); } if (foundPtr == null ) { if (temp5.child != null ) { Find(temp5.child, old_val, val); } if ((temp5.right).c != 'Y' ) { Find(temp5.right, old_val, val); } } temp5.c = 'N' ; found = foundPtr; } // Deleting a node from the heap static void Deletion( int val) { if (mini == null ) { Console.WriteLine( "The heap is empty" ); } else { // Decreasing the value of the // node to 0 Find(mini, val, 0); // Calling Extract_min function to // delete minimum value node, // which is 0 Extract_min(); Console.WriteLine( "Key Deleted" ); } } // Function to display the heap static void display() { Node ptr = mini; if (ptr == null ) { Console.WriteLine( "The Heap is Empty" ); } else { Console.WriteLine( "The root nodes of Heap are: " ); do { Console.Write(ptr.key); ptr = ptr.right; if (ptr != mini) { Console.Write( "-->" ); } } while (ptr != mini && ptr.right != null ); Console.WriteLine(); Console.WriteLine( "The heap has " + no_of_nodes + " node" ); Console.WriteLine(); } } // Driver code static void Main( string [] args) { // We will create a heap and insert // 3 nodes into it Console.WriteLine( "Creating an initial heap" ); insertion(5); insertion(2); insertion(8); // We will create a heap and insert // 3 nodes into it display(); // Now we will delete the node '7' Console.WriteLine( "Delete the node 8" ); Deletion(8); Console.WriteLine( "Delete the node 5" ); Deletion(5); display(); } } // This Code is Contributed by Prajwal Kandekar |
Javascript
// Creating a class to represent a node in the heap class Node { constructor() { this .parent = null ; this .child = null ; this .left = null ; this .right = null ; this .key = 0; this .degree = 0; this .mark = 'W' ; this .c = 'N' ; } } // Creating a class for Fibonacci Heap class FibonacciHeap { constructor() { this .mini = null ; this .no_of_nodes = 0; } // Function to insert a node in heap insertion(val) { const new_node = new Node(); new_node.key = val; new_node.degree = 0; new_node.mark = 'W' ; new_node.c = 'N' ; new_node.parent = null ; new_node.child = null ; new_node.left = new_node; new_node.right = new_node; if ( this .mini !== null ) { this .mini.left.right = new_node; new_node.right = this .mini; new_node.left = this .mini.left; this .mini.left = new_node; if (new_node.key < this .mini.key) this .mini = new_node; } else { this .mini = new_node; } this .no_of_nodes++; } // Other methods like Fibonnaci_link, Consolidate, Extract_min, Cut, Cascade_cut, Decrease_key, Find, Deletion, display go here... // Function to display the heap display() { let ptr = this .mini; if (ptr === null ) { console.log( "The Heap is Empty" ); } else { console.log( "The root nodes of Heap are: " ); do { process.stdout.write(ptr.key.toString()); ptr = ptr.right; if (ptr !== this .mini) { process.stdout.write( "-->" ); } } while (ptr !== this .mini && ptr.right !== null ); console.log(); console.log(`The heap has ${ this .no_of_nodes} nodes`); console.log(); } } } // Driver code const fibonacciHeap = new FibonacciHeap(); console.log( "Creating an initial heap" ); fibonacciHeap.insertion(5); fibonacciHeap.insertion(2); fibonacciHeap.insertion(8); // Display the root list of the heap fibonacciHeap.display(); // Delete the node '8' console.log( "Delete the node 8" ); // Implement Deletion method here by calling Deletion(8) on the FibonacciHeap object // fibonacciHeap.Deletion(8); // Delete the node '5' console.log( "Delete the node 5" ); // Implement Deletion method here by calling Deletion(5) on the FibonacciHeap object // fibonacciHeap.Deletion(5); // Display the heap after deletion fibonacciHeap.display(); |
Creating an initial heap The root nodes of Heap are: 2-->5-->8 The heap has 3 node Delete the node 8 Key Deleted Delete the node 5 Key Deleted The root nodes of Heap are: 2 The heap has 1 node
Binomial Heap:
A binomial heap is a heap similar to a binary heap but also supports quick merging of two heaps. It is implemented using a binomial tree. Each node in a binomial tree has exactly one child.
- Insertion in Binomial Heap:
Insertion in a binomial heap is done by creating a new binomial tree with the key of the inserted element and then merging it with the existing binomial trees. - Deletion in Binomial Heap:
Deletion in a binomial heap is done by first removing the element to be deleted from the root list and then merging its children into the root list. The resulting heap is then consolidated by repeatedly merging roots of the same degree.
Following is a C++ program to demonstrate Insertion() and DeleteMin() operations on a Binomial Heap:
C++
// C++ program to implement different // operations on Binomial Heap #include <bits/stdc++.h> using 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*> DeleteMin(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 CODE 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\nMinimum element of heap " << temp->data << "\n" ; // Delete minimum element of heap _heap = DeleteMin(_heap); cout << "\nHeap after deletion of minimum element\n" ; printHeap(_heap); return 0; } |
Java
import java.util.ArrayList; import java.util.Collections; import java.util.List; class Node { int data; Node parent, sibling, child; int degree; public Node( int data) { this .data = data; this .parent = null ; this .sibling = null ; this .child = null ; this .degree = 0 ; } } public class BinomialHeap { public static Node newNode( int key) { return new Node(key); } public static List<Node> insertATreeInHeap(List<Node> heap, Node tree) { List<Node> newHeap = unionBionomialHeap( heap, Collections.singletonList(tree)); return newHeap; } public static Node getMin(List<Node> heap) { Node temp = heap.get( 0 ); for (Node node : heap) { if (node.data < temp.data) { temp = node; } } return temp; } public static List<Node> removeMinFromTreeReturnBHeap(Node node) { List<Node> newHeap = new ArrayList<>(); if (node.child != null ) { Node child = node.child; node.child = null ; while (child != null ) { child.parent = null ; newHeap.add(child); child = child.sibling; } Collections.reverse(newHeap); } return newHeap; } public static List<Node> unionBionomialHeap(List<Node> heap1, List<Node> heap2) { List<Node> resHeap = new ArrayList<>(); int i = 0 , j = 0 ; while (i < heap1.size() && j < heap2.size()) { if (heap1.get(i).degree <= heap2.get(j).degree) { resHeap.add(heap1.get(i)); i++; } else { resHeap.add(heap2.get(j)); j++; } } while (i < heap1.size()) { resHeap.add(heap1.get(i)); i++; } while (j < heap2.size()) { resHeap.add(heap2.get(j)); j++; } return resHeap; } public static void link(Node node1, Node node2) { node1.parent = node2; node1.sibling = node2.child; node2.child = node1; node2.degree += 1 ; } public static List<Node> adjust(List<Node> heap) { if (heap.isEmpty()) { return heap; } Collections.sort(heap, (a, b) -> a.degree - b.degree); List<Node> newHeap = new ArrayList<>(); newHeap.add(heap.get( 0 )); for ( int i = 1 ; i < heap.size(); i++) { if (newHeap.get(newHeap.size() - 1 ).degree == heap.get(i).degree) { if (i + 1 < heap.size() && heap.get(i + 1 ).degree == heap.get(i).degree) { newHeap.add(heap.get(i)); } else { link(heap.get(i), newHeap.get(newHeap.size() - 1 )); } } else { newHeap.add(heap.get(i)); } } return newHeap; } public static List<Node> insert(List<Node> heap, int key) { Node temp = newNode(key); return insertATreeInHeap(heap, temp); } public static List<Node> deleteMin(List<Node> heap) { List<Node> newHeap = new ArrayList<>(); Node temp = getMin(heap); for (Node node : heap) { if (node != temp) { newHeap.add(node); } } List<Node> lo = removeMinFromTreeReturnBHeap(temp); newHeap = unionBionomialHeap(newHeap, lo); newHeap = adjust(newHeap); return newHeap; } public static void printTree(Node h) { while (h != null ) { System.out.print(h.data + " " ); printTree(h.child); h = h.sibling; } } public static void printHeap(List<Node> heap) { for (Node node : heap) { printTree(node); } } public static void main(String[] args) { List<Node> heap = new ArrayList<>(); heap = insert(heap, 10 ); heap = insert(heap, 20 ); heap = insert(heap, 30 ); System.out.println( "Heap elements after insertion:" ); printHeap(heap); Node temp = getMin(heap); System.out.println( "\nMinimum element of heap: " + temp.data); heap = deleteMin(heap); System.out.println( "Heap after deletion of minimum element:" ); printHeap(heap); } } // This Code is contributed by Gaurav_Arora |
Python3
# Python program to implement different # operations on Binomial Heap # A Binomial Tree node. class Node: def __init__( self , data): self .data = data self .parent = None self .sibling = None self .child = None self .degree = 0 def newNode(key): return Node(key) def insertATreeInHeap(heap, tree): return unionBionomialHeap(heap, [tree]) def getMin(heap): temp = heap[ 0 ] for node in heap: if node.data < temp.data: temp = node return temp def removeMinFromTreeReturnBHeap(node): new_heap = [] if node.child: child = node.child node.child = None while child: child.parent = None new_heap.append(child) child = child.sibling new_heap = reverse(new_heap) return new_heap # This function perform union operation # on two binomial heap i.e. l1 & l2 def unionBionomialHeap(heap1, heap2): # _new to another binomial heap which # contain new heap after merging l1 & l2 res_heap = [] i, j = 0 , 0 while i < len (heap1) and j < len (heap2): if heap1[i].degree < = heap2[j].degree: res_heap.append(heap1[i]) i + = 1 else : res_heap.append(heap2[j]) j + = 1 # If there remains some elements # in l1 binomial heap while i < len (heap1): res_heap.append(heap1[i]) i + = 1 # If there remains some elements # in l2 binomial heap while j < len (heap2): res_heap.append(heap2[j]) j + = 1 return res_heap def link(node1, node2): node1.parent = node2 node1.sibling = node2.child node2.child = node1 node2.degree + = 1 # 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 def adjust(heap): if not heap: # If only one element remains # to be processed return heap heap = sorted (heap, key = lambda x: x.degree) new_heap = [heap[ 0 ]] for i in range ( 1 , len (heap)): if new_heap[ - 1 ].degree = = heap[i].degree: if i + 1 < len (heap) and heap[i + 1 ].degree = = heap[i].degree: new_heap.append(heap[i]) else : link(heap[i], new_heap[ - 1 ]) else : new_heap.append(heap[i]) return new_heap def insert(heap, key): temp = newNode(key) return insertATreeInHeap(heap, temp) def DeleteMin(heap): new_heap = [] # Temp contains the pointer of # minimum value element in heap temp = getMin(heap) for node in heap: if node ! = temp: # Inserting all Binomial Tree # into new binomial heap except # the Binomial Tree contains # minimum element new_heap.append(node) lo = removeMinFromTreeReturnBHeap(temp) new_heap = unionBionomialHeap(new_heap, lo) new_heap = adjust(new_heap) return new_heap # Print function for Binomial Tree def printTree(h): while h: print (h.data, end = " " ) printTree(h.child) h = h.sibling # Print function for binomial heap def printHeap(heap): for node in heap: printTree(node) # Driver CODE if __name__ = = "__main__" : heap = [] # Insert data in the heap heap = insert(heap, 10 ) heap = insert(heap, 20 ) heap = insert(heap, 30 ) print ( "Heap elements after insertion:" ) printHeap(heap) temp = getMin(heap) print ( "\nMinimum element of heap" , temp.data) # Delete minimum element of heap heap = DeleteMin(heap) print ( "Heap after deletion of minimum element" ) printHeap(heap) # Contributed by sdeadityasharma |
C#
using System; using System.Collections.Generic; // A Binomial Tree node. public class Node { public int data; public Node parent, sibling, child; public int degree; public Node( int key) { data = key; parent = sibling = child = null ; degree = 0; } } public class BinomialHeap { // This function inserts a Binomial Tree into the binomial heap private static List<Node> InsertATreeInHeap(List<Node> heap, Node tree) { return UnionBionomialHeap(heap, new List<Node> { tree }); } // This function returns a pointer to the minimum value Node present in the binomial heap private static Node GetMin(List<Node> heap) { Node temp = heap[0]; foreach ( var node in heap) { if (node.data < temp.data) { temp = node; } } return temp; } // This function removes the minimum key element from the binomial heap // and returns the binomial heap after removing the head of that tree i.e. the minimum element private static List<Node> RemoveMinFromTreeReturnBHeap(Node node) { List<Node> newHeap = new List<Node>(); if (node.child != null ) { Node child = node.child; node.child = null ; while (child != null ) { child.parent = null ; newHeap.Insert(0, child); child = child.sibling; } newHeap = Reverse(newHeap); } return newHeap; } // This function performs the union operation on two binomial heaps i.e. l1 & l2 private static List<Node> UnionBionomialHeap(List<Node> heap1, List<Node> heap2) { List<Node> resultHeap = new List<Node>(); int i = 0, j = 0; while (i < heap1.Count && j < heap2.Count) { if (heap1[i].degree <= heap2[j].degree) { resultHeap.Add(heap1[i]); i++; } else { resultHeap.Add(heap2[j]); j++; } } // If there remain some elements in l1 binomial heap while (i < heap1.Count) { resultHeap.Add(heap1[i]); i++; } // If there remain some elements in l2 binomial heap while (j < heap2.Count) { resultHeap.Add(heap2[j]); j++; } return resultHeap; } // Adjust function rearranges the heap // so that heap is in increasing order // of degree and no two binomial trees // have the same degree in this heap private static List<Node> Adjust(List<Node> heap) { if (heap.Count < 2) { // If only one element remains to be processed return heap; } heap.Sort((x, y) => x.degree.CompareTo(y.degree)); List<Node> newHeap = new List<Node> { heap[0] }; for ( int i = 1; i < heap.Count; i++) { if (newHeap[newHeap.Count - 1].degree == heap[i].degree) { if (i + 1 < heap.Count && heap[i + 1].degree == heap[i].degree) { newHeap.Add(heap[i]); } else { Link(heap[i], newHeap[newHeap.Count - 1]); } } else { newHeap.Add(heap[i]); } } return newHeap; } // This function inserts a key into the binomial heap public static List<Node> Insert(List<Node> heap, int key) { Node temp = new Node(key); return InsertATreeInHeap(heap, temp); } // This function deletes the minimum element of the heap public static List<Node> DeleteMin(List<Node> heap) { List<Node> newHeap = new List<Node>(); // Temp contains the pointer of the minimum value element in the heap Node temp = GetMin(heap); foreach ( var node in heap) { if (node != temp) { // Inserting all Binomial Trees into the new binomial heap except // the Binomial Tree that contains the minimum element newHeap.Add(node); } } List<Node> lo = RemoveMinFromTreeReturnBHeap(temp); newHeap = UnionBionomialHeap(newHeap, lo); newHeap = Adjust(newHeap); return newHeap; } // Print function for Binomial Tree private static void PrintTree(Node h) { while (h != null ) { Console.Write(h.data + " " ); PrintTree(h.child); h = h.sibling; } } // Print function for binomial heap public static void PrintHeap(List<Node> heap) { foreach ( var node in heap) { PrintTree(node); } } // Driver CODE public static void Main() { List<Node> heap = new List<Node>(); // Insert data into the heap heap = Insert(heap, 10); heap = Insert(heap, 20); heap = Insert(heap, 30); Console.WriteLine( "Heap elements after insertion:" ); PrintHeap(heap); Node temp = GetMin(heap); Console.WriteLine($ "\n\nMinimum element of the heap: {temp.data}" ); // Delete the minimum element of the heap heap = DeleteMin(heap); Console.WriteLine( "Heap after deletion of the minimum element:" ); PrintHeap(heap); } private static List<Node> Reverse(List<Node> list) { list.Reverse(); return list; } private static void Link(Node node1, Node node2) { node1.parent = node2; node1.sibling = node2.child; node2.child = node1; node2.degree += 1; } } |
Javascript
class Node { constructor(data) { this .data = data; this .parent = null ; this .sibling = null ; this .child = null ; this .degree = 0; } } // Function to create a new node with a given key function newNode(key) { return new Node(key); } // Function to insert a tree into the heap function insertATreeInHeap(heap, tree) { return unionBionomialHeap(heap, [tree]); } // Function to find the minimum node in the heap function getMin(heap) { let temp = heap[0]; for (const node of heap) { if (node.data < temp.data) { temp = node; } } return temp; } // Function to remove the minimum node from a tree and return the resulting heap function removeMinFromTreeReturnBHeap(node) { const newHeap = []; if (node.child !== null ) { let child = node.child; node.child = null ; // Traverse the children and add them to the new heap while (child !== null ) { child.parent = null ; newHeap.push(child); child = child.sibling; } newHeap.reverse(); // Reverse the order to maintain the correct degree order } return newHeap; } // Function to merge two binomial heaps function unionBionomialHeap(heap1, heap2) { const resHeap = []; let i = 0, j = 0; // Merge the two heaps in a sorted order of degrees while (i < heap1.length && j < heap2.length) { if (heap1[i].degree <= heap2[j].degree) { resHeap.push(heap1[i]); i++; } else { resHeap.push(heap2[j]); j++; } } // Add the remaining elements from heap1 while (i < heap1.length) { resHeap.push(heap1[i]); i++; } // Add the remaining elements from heap2 while (j < heap2.length) { resHeap.push(heap2[j]); j++; } return resHeap; } // Function to link two binomial trees function link(node1, node2) { node1.parent = node2; node1.sibling = node2.child; node2.child = node1; node2.degree += 1; } // Function to adjust the heap after an operation function adjust(heap) { if (heap.length === 0) { return heap; } // Sort the heap based on degrees heap.sort((a, b) => a.degree - b.degree); const newHeap = [heap[0]]; // Merge nodes with the same degree for (let i = 1; i < heap.length; i++) { if (newHeap[newHeap.length - 1].degree === heap[i].degree) { if (i + 1 < heap.length && heap[i + 1].degree === heap[i].degree) { newHeap.push(heap[i]); } else { link(heap[i], newHeap[newHeap.length - 1]); } } else { newHeap.push(heap[i]); } } return newHeap; } // Function to insert a key into the heap function insert(heap, key) { const temp = newNode(key); return insertATreeInHeap(heap, temp); } // Function to delete the minimum node from the heap function deleteMin(heap) { const newHeap = []; const temp = getMin(heap); // Remove the minimum node from the heap for (const node of heap) { if (node !== temp) { newHeap.push(node); } } const lo = removeMinFromTreeReturnBHeap(temp); // Adjust the heap after deletion return adjust(unionBionomialHeap(newHeap, lo)); } // Function to print a tree function printTree(h) { while (h !== null ) { process.stdout.write(h.data + ' ' ); printTree(h.child); h = h.sibling; } } // Function to print the entire heap function printHeap(heap) { for (const node of heap) { printTree(node); } } // Main program let heap = []; heap = insert(heap, 10); heap = insert(heap, 20); heap = insert(heap, 30); console.log( "Heap elements after insertion:" ); printHeap(heap); const temp = getMin(heap); console.log( "\nMinimum element of heap: " + temp.data); heap = deleteMin(heap); console.log( "Heap after deletion of minimum element:" ); printHeap(heap); |
Heap elements after insertion: 30 10 20 Minimum element of heap 10 Heap after deletion of minimum element 20 30
Conclusion:
Fibonacci heap and binomial heap are efficient data structures for implementing priority queues. Insertion and deletion in these data structures can be done in logarithmic time. However, the Fibonacci heap has better-amortized running time and is generally considered to be more efficient than a binomial heap.