In vorig bericht d.w.z. Set 1 die we hebben besproken en die deze onderstaande functies implementeert:
- invoegen(Hk): Voegt een sleutel ‘k’ in voor binomiale hoop ‘H’. Deze bewerking creëert eerst een binomiale heap met enkele sleutel ‘k’ en roept vervolgens unie op H en de nieuwe binomiale heap aan.
- krijgMin(H): Een eenvoudige manier om getMin() te verkrijgen is door de lijst met root-bestanden van binomiale bomen te doorlopen en de minimumsleutel terug te geven. Deze implementatie vereist O(Logn)-tijd. Het kan worden geoptimaliseerd tot O(1) door een verwijzing naar de minimale sleutelwortel te behouden.
- extractMin(H): Deze bewerking maakt ook gebruik van union(). We roepen eerst getMin() aan om de binomiale boom met de minimumsleutel te vinden, daarna verwijderen we het knooppunt en creëren we een nieuwe binomiale heap door alle subbomen van het verwijderde minimumknooppunt met elkaar te verbinden. Ten slotte roepen we union() aan op H en de nieuw gemaakte binomiale heap. Deze bewerking vereist O(Logn)-tijd.
Voorbeelden:
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
In dit bericht zijn onderstaande functies geïmplementeerd.
- verwijderen(H): Net als bij de verwijderbewerking van Binary Heap wordt eerst de sleutel teruggebracht tot minus oneindig en wordt vervolgens extractMin() aangeroepen.
- sleutel verlagen(H): afnameKey() is ook vergelijkbaar met Binary Heap. We vergelijken de sleutel voor afnemen met de ouder en als de sleutel van de ouder groter is, wisselen we de sleutels om en herhalen we deze voor de ouder. We stoppen wanneer we een knooppunt bereiken waarvan de ouder een kleinere sleutel heeft, of wanneer we het hoofdknooppunt bereiken. Tijdcomplexiteit van afnameKey() is O(Logn)
Uitvoering:
C++// C++ program for implementation of // Binomial Heap and Operations on it #include
import java.util.ArrayList; import java.util.List; // Structure of Node class Node { int val degree; Node parent child sibling; } // Class to represent a Binomial Heap class BinomialHeap { private Node root; // Making root global to avoid one extra parameter in all functions. public BinomialHeap() { this.root = null; } // Link two heaps by making h1 a child of h2. private void binomialLink(Node h1 Node h2) { h1.parent = h2; h1.sibling = h2.child; h2.child = h1; h2.degree = h2.degree + 1; } // Create a Node private Node createNode(int n) { Node new_node = new Node(); new_node.val = n; new_node.parent = null; new_node.sibling = null; new_node.child = null; new_node.degree = 0; return new_node; } // This function merge two Binomial Trees private Node mergeBHeaps(Node h1 Node h2) { if (h1 == null) return h2; if (h2 == null) return h1; // Define a Node Node res; // Check degree of both Node i.e. which is greater or smaller if (h1.degree <= h2.degree) res = h1; else res = h2; // Traverse till if any of the heap gets empty while (h1 != null && h2 != null) { // If degree of h1 is smaller increment h1 if (h1.degree < h2.degree) h1 = h1.sibling; // Link h1 with h2 in case of equal degree else if (h1.degree == h2.degree) { Node sib = h1.sibling; h1.sibling = h2; h1 = sib; } // If h2 is greater else { Node sib = h2.sibling; h2.sibling = h1; h2 = sib; } } return res; } // This function performs the union operation on two binomial heaps i.e. h1 & h2 private Node unionBHeaps(Node h1 Node h2) { if (h1 == null && h2 == null) return null; Node res = mergeBHeaps(h1 h2); // Traverse the merged list and set values according to the degree of Nodes Node prev = null curr = res next = curr.sibling; while (next != null) { if ((curr.degree != next.degree) || ((next.sibling != null) && (next.sibling).degree == curr.degree)) { prev = curr; curr = next; } else { if (curr.val <= next.val) { curr.sibling = next.sibling; binomialLink(next curr); } else { if (prev == null) res = next; else prev.sibling = next; binomialLink(curr next); curr = next; } } next = curr.sibling; } return res; } // Function to insert a Node public void binomialHeapInsert(int x) { // Create a new node and do union of this node with root root = unionBHeaps(root createNode(x)); } // Function to display the Nodes private void display(Node h) { while (h != null) { System.out.print(h.val + ' '); display(h.child); h = h.sibling; } } // Function to reverse a list using recursion. private Node revertList(Node h) { if (h.sibling != null) { revertList(h.sibling); (h.sibling).sibling = h; } else root = h; return root; } // Function to extract the minimum value private Node extractMinBHeap(Node h) { if (h == null) return null; Node min_node_prev = null; Node min_node = h; // Find the minimum value int min = h.val; Node curr = h; while (curr.sibling != null) { if ((curr.sibling).val < min) { min = (curr.sibling).val; min_node_prev = curr; min_node = curr.sibling; } curr = curr.sibling; } // If there is a single Node if (min_node_prev == null && min_node.sibling == null) h = null; else if (min_node_prev == null) h = min_node.sibling; // Remove the min node from the list else min_node_prev.sibling = min_node.sibling; // Set root (which is global) as children list of min node if (min_node.child != null) { revertList(min_node.child); (min_node.child).sibling = null; } else root = null; return unionBHeaps(h root); } // Function to search for an element private Node findNode(Node h int val) { if (h == null) return null; // Check if key is equal to the root's data if (h.val == val) return h; // Recur for child Node res = findNode(h.child val); if (res != null) return res; return findNode(h.sibling val); } // Function to decrease the value of old_val to new_val private void decreaseKeyBHeap(Node H int old_val int new_val) { // First check if the Node is present Node node = findNode(H old_val); // Return if Node is not present if (node == null) return; // Reduce the value to the minimum node.val = new_val; Node parent = node.parent; // Update the heap according to the reduced value while (parent != null && node.val < parent.val) { int temp = node.val; node.val = parent.val; parent.val = temp; node = parent; parent = parent.parent; } } // Function to delete an element public void binomialHeapDelete(int val) { // Check if the heap is empty or not if (root == null) return; // Reduce the value of element to minimum decreaseKeyBHeap(root val Integer.MIN_VALUE); // Delete the minimum element from the heap root = extractMinBHeap(root); } // Driver code public static void main(String[] args) { BinomialHeap heap = new BinomialHeap(); heap.binomialHeapInsert(10); heap.binomialHeapInsert(20); heap.binomialHeapInsert(30); heap.binomialHeapInsert(40); heap.binomialHeapInsert(50); System.out.println('The heap is:'); heap.display(heap.root); // Delete a particular element from the heap heap.binomialHeapDelete(10); System.out.println('nAfter deleting 10 the heap is:'); heap.display(heap.root); } }
# python program for implementation of # Binomial Heap and Operations on it INT_MIN = -2147483648; g = 0 # Structure of Node class Node: def __init__(self): self.val = 0; self.degree = 0; self.parent = None; self.child = None; self.sibling = None; # Making root global to avoid one extra # parameter in all functions. root = None; # link two heaps by making h1 a child # of h2. def binomialLink(h1 h2): h1.parent = h2; h1.sibling = h2.child; h2.child = h1; h2.degree = h2.degree + 1; return -1; # create a Node def createNode(n): new_node = Node(); new_node.val = n; new_node.parent = None; new_node.sibling = None; new_node.child = None; new_node.degree = 0; return new_node; # This function merge two Binomial Trees def mergeBHeaps(h1 h2): if (h1 == None): return h2; if (h2 == None): return h1; # define a Node res = None; # check degree of both Node i.e. # which is greater or smaller if (h1.degree <= h2.degree): res = h1; elif(h1.degree > h2.degree): res = h2; # traverse till if any of heap gets empty while (h1 != None and h2 != None): # if degree of h1 is smaller increment h1 if (h1.degree < h2.degree): h1 = h1.sibling; # Link h1 with h2 in case of equal degree elif(h1.degree == h2.degree): sib = h1.sibling; h1.sibling = h2; h1 = sib; # if h2 is greater else: sib = h2.sibling; h2.sibling = h1; h2 = sib; return res; # This function perform union operation on two # binomial heap i.e. h1 & h2 def unionBHeaps(h1 h2): # global root if (h1 == None and h2 == None): return None; res = mergeBHeaps(h1 h2); # Traverse the merged list and set # values according to the degree of # Nodes prev = None; curr = res; next = curr.sibling; while (next != None): if ((curr.degree != next.degree) or ((next.sibling != None) and (next.sibling).degree == curr.degree)): prev = curr; curr = next; else: if (curr.val <= next.val): curr.sibling = next.sibling; binomialLink(next curr); else: if (prev == None): res = next; else: prev.sibling = next; binomialLink(curr next); curr = next; next = curr.sibling; return res; # Function to insert a Node def binomialHeapInsert(x): # Create a new node and do union of # this node with root global root root = unionBHeaps(root createNode(x)); # Function to display the Nodes def display(h): global g while (h): if g != 1 or h.val != 10: print(h.valend = ' '); display(h.child); h = h.sibling; # Function to reverse a list # using recursion. def revertList(h): if (h.sibling != None): revertList(h.sibling); (h.sibling).sibling = h; else: root = h; return -1; # Function to extract minimum value def extractMinBHeap(h): global root if (h == None): return None; min_node_prev = None; min_node = h; # Find minimum value min = h.val; curr = h; while (curr.sibling != None): if ((curr.sibling).val < min): min = (curr.sibling).val; min_node_prev = curr; min_node = curr.sibling; curr = curr.sibling; # If there is a single Node if (min_node_prev == None and min_node.sibling == None): h = None; elif(min_node_prev == None): h = min_node.sibling; # Remove min node from list else: min_node_prev.sibling = min_node.sibling; # Set root (which is global) as children # list of min node if (min_node.child != None): revertList(min_node.child); (min_node.child).sibling = None; else: root = None; del min_node; # Do union of root h and children return unionBHeaps(h root); # Function to search for an element def findNode( h val): if (h == None): return None; # check if key is equal to the root's data if (h.val == val): return h; # Recur for child res = findNode(h.child val); if (res != None): return res; return findNode(h.sibling val); # Function to decrease the value of old_val # to new_val def decreaseKeyBHeap(H old_val new_val): # First check element present or not node = findNode(H old_val); # return if Node is not present if (node == None): return; # Reduce the value to the minimum node.val = new_val; parent = node.parent; # Update the heap according to reduced value while (parent != None and node.val < parent.val): temp = node.val; node.val = parent.val; parent.val = temp; node = parent; parent = parent.parent; # Function to delete an element def binomialHeapDelete( h val): global root; return root; # Check if heap is empty or not if (h == None): return None; # Reduce the value of element to minimum decreaseKeyBHeap(h val INT_MIN); # Delete the minimum element from heap return extractMinBHeap(h); #Driver code #Note that root is global binomialHeapInsert(10); binomialHeapInsert(20); binomialHeapInsert(30); binomialHeapInsert(40); binomialHeapInsert(50); print('The heap is:'); display(root); #Delete a particular element from heap root = binomialHeapDelete(root 10); print('nAfter deleting 10 the heap is:'); # stores bool g = 1 # display display(root); #The code is contributed by Nidhi goel.
using System; class BinomialHeap { class Node { public int val degree; public Node parent child sibling; } static Node root = null; static int BinomialLink(Node h1 Node h2) { h1.parent = h2; h1.sibling = h2.child; h2.child = h1; h2.degree = h2.degree + 1; return 0; } static Node CreateNode(int n) { Node newNode = new Node(); newNode.val = n; newNode.parent = null; newNode.sibling = null; newNode.child = null; newNode.degree = 0; return newNode; } static Node MergeBHeaps(Node h1 Node h2) { if (h1 == null) return h2; if (h2 == null) return h1; Node res = null; if (h1.degree <= h2.degree) res = h1; else if (h1.degree > h2.degree) res = h2; while (h1 != null && h2 != null) { if (h1.degree < h2.degree) h1 = h1.sibling; else if (h1.degree == h2.degree) { Node sib = h1.sibling; h1.sibling = h2; h1 = sib; } else { Node sib = h2.sibling; h2.sibling = h1; h2 = sib; } } return res; } static Node UnionBHeaps(Node h1 Node h2) { if (h1 == null && h2 == null) return null; Node res = MergeBHeaps(h1 h2); Node prev = null curr = res next = curr.sibling; while (next != null) { if ((curr.degree != next.degree) || ((next.sibling != null) && (next.sibling).degree == curr.degree)) { prev = curr; curr = next; } else { if (curr.val <= next.val) { curr.sibling = next.sibling; BinomialLink(next curr); } else { if (prev == null) res = next; else prev.sibling = next; BinomialLink(curr next); curr = next; } } next = curr.sibling; } return res; } static void BinomialHeapInsert(int x) { root = UnionBHeaps(root CreateNode(x)); } static void Display(Node h) { while (h != null) { Console.Write(h.val + ' '); Display(h.child); h = h.sibling; } } static int RevertList(Node h) { if (h.sibling != null) { RevertList(h.sibling); (h.sibling).sibling = h; } else root = h; return 0; } static Node ExtractMinBHeap(Node h) { if (h == null) return null; Node minNodePrev = null; Node minNode = h; int min = h.val; Node curr = h; while (curr.sibling != null) { if ((curr.sibling).val < min) { min = (curr.sibling).val; minNodePrev = curr; minNode = curr.sibling; } curr = curr.sibling; } if (minNodePrev == null && minNode.sibling == null) h = null; else if (minNodePrev == null) h = minNode.sibling; else minNodePrev.sibling = minNode.sibling; if (minNode.child != null) { RevertList(minNode.child); (minNode.child).sibling = null; } else root = null; // Delete minNode to avoid memory leak minNode = null; return UnionBHeaps(h root); } static Node FindNode(Node h int val) { if (h == null) return null; if (h.val == val) return h; Node res = FindNode(h.child val); if (res != null) return res; return FindNode(h.sibling val); } static void DecreaseKeyBHeap(Node H int oldVal int newVal) { Node node = FindNode(H oldVal); if (node == null) return; node.val = newVal; Node parent = node.parent; while (parent != null && node.val < parent.val) { Swap(ref node.val ref parent.val); node = parent; parent = parent.parent; } } static Node BinomialHeapDelete(Node h int val) { if (h == null) return null; DecreaseKeyBHeap(h val int.MinValue); return ExtractMinBHeap(h); } static void Swap(ref int a ref int b) { int temp = a; a = b; b = temp; } static void Main() { BinomialHeapInsert(10); BinomialHeapInsert(20); BinomialHeapInsert(30); BinomialHeapInsert(40); BinomialHeapInsert(50); Console.WriteLine('The heap is:'); Display(root); root = BinomialHeapDelete(root 10); Console.WriteLine( 'nAfter deleting 10 the heap is:'); Display(root); } }
// javascript program for implementation of // Binomial Heap and Operations on it const INT_MIN = -2147483648; // Structure of Node class Node { constructor(){ this.val = 0; this.degree = 0; this.parent = null; this.child = null; this.sibling = null; } } // Making root global to avoid one extra // parameter in all functions. let root = null; // link two heaps by making h1 a child // of h2. function binomialLink(h1 h2) { h1.parent = h2; h1.sibling = h2.child; h2.child = h1; h2.degree = h2.degree + 1; return -1; } // create a Node function createNode(n) { let new_node = new Node; new_node.val = n; new_node.parent = null; new_node.sibling = null; new_node.child = null; new_node.degree = 0; return new_node; } // This function merge two Binomial Trees function mergeBHeaps(h1 h2) { if (h1 == null) return h2; if (h2 == null) return h1; // define a Node let res = null; // check degree of both Node i.e. // which is greater or smaller if (h1.degree <= h2.degree) res = h1; else if (h1.degree > h2.degree) res = h2; // traverse till if any of heap gets empty while (h1 != null && h2 != null) { // if degree of h1 is smaller increment h1 if (h1.degree < h2.degree) h1 = h1.sibling; // Link h1 with h2 in case of equal degree else if (h1.degree == h2.degree) { let sib = h1.sibling; h1.sibling = h2; h1 = sib; } // if h2 is greater else { let sib = h2.sibling; h2.sibling = h1; h2 = sib; } } return res; } // This function perform union operation on two // binomial heap i.e. h1 & h2 function unionBHeaps(h1 h2) { if (h1 == null && h2 == null) return null; let res = mergeBHeaps(h1 h2); // Traverse the merged list and set // values according to the degree of // Nodes let prev = null; let curr = res; let next = curr.sibling; while (next != null) { if ((curr.degree != next.degree) || ((next.sibling != null) && (next.sibling).degree == curr.degree)) { prev = curr; curr = next; } else { if (curr.val <= next.val) { curr.sibling = next.sibling; binomialLink(next curr); } else { if (prev == null) res = next; else prev.sibling = next; binomialLink(curr next); curr = next; } } next = curr.sibling; } return res; } // Function to insert a Node function binomialHeapInsert(x) { // Create a new node and do union of // this node with root root = unionBHeaps(root createNode(x)); } // Function to display the Nodes function display(h) { while (h) { process.stdout.write(h.val + ' '); display(h.child); h = h.sibling; } } // Function to reverse a list // using recursion. function revertList(h) { if (h.sibling != null) { revertList(h.sibling); (h.sibling).sibling = h; } else root = h; return -1; } // Function to extract minimum value function extractMinBHeap(h) { if (h == null) return null; let min_node_prev = null; let min_node = h; // Find minimum value let min = h.val; let curr = h; while (curr.sibling != null) { if ((curr.sibling).val < min) { min = (curr.sibling).val; min_node_prev = curr; min_node = curr.sibling; } curr = curr.sibling; } // If there is a single Node if (min_node_prev == null && min_node.sibling == null) h = null; else if (min_node_prev == null) h = min_node.sibling; // Remove min node from list else min_node_prev.sibling = min_node.sibling; // Set root (which is global) as children // list of min node if (min_node.child != null) { revertList(min_node.child); (min_node.child).sibling = null; } else root = null; delete min_node; // Do union of root h and children return unionBHeaps(h root); } // Function to search for an element function findNode( h val) { if (h == null) return null; // check if key is equal to the root's data if (h.val == val) return h; // Recur for child let res = findNode(h.child val); if (res != null) return res; return findNode(h.sibling val); } // Function to decrease the value of old_val // to new_val function decreaseKeyBHeap(H old_val new_val) { // First check element present or not let node = findNode(H old_val); // return if Node is not present if (node == null) return; // Reduce the value to the minimum node.val = new_val; let parent = node.parent; // Update the heap according to reduced value while (parent != null && node.val < parent.val) { let temp = node.val; node.val = parent.val; parent.val = temp; node = parent; parent = parent.parent; } } // Function to delete an element function binomialHeapDelete( h val) { // Check if heap is empty or not if (h == null) return null; // Reduce the value of element to minimum decreaseKeyBHeap(h val INT_MIN); // Delete the minimum element from heap return extractMinBHeap(h); } // Driver code // Note that root is global binomialHeapInsert(10); binomialHeapInsert(20); binomialHeapInsert(30); binomialHeapInsert(40); binomialHeapInsert(50); console.log('The heap is:'); display(root); // Delete a particular element from heap root = binomialHeapDelete(root 10); console.log('nAfter deleting 10 the heap is:'); display(root); //The code is contributed by Nidhi goel.
Uitvoer
The heap is: 50 10 30 40 20 After deleting 10 the heap is: 20 30 40 50Quiz maken