DAA_Unit-4.pdf

Red-Black Tree Source: Internet, reference books, NPTEL Definition  Binary search trees are a fundamental data structure, but their performance can suffer if the tree becomes unbalanced.  Red Black Trees are a type of balanced binary search tree that use a se...

Red-Black Tree Source: Internet, reference books, NPTEL Definition  Binary search trees are a fundamental data structure, but their performance can suffer if the tree becomes unbalanced.  Red Black Trees are a type of balanced binary search tree that use a set of rules to maintain balance, ensuring logarithmic time complexity for operations like insertion, deletion, and searching, regardless of the initial shape of the tree.  Red Black Trees are self-balancing, using a simple color-coding scheme to adjust the tree after each modification.  A Red-Black Tree is a self-balancing binary search tree where each node has an additional attribute: a color, which can be either red or black.  The primary objective of these trees is to maintain balance during insertions and deletions, ensuring efficient data retrieval and manipulation. 2 Properties of Red-Black Trees A Red-Black Tree have the following properties: 1. Node Color: Each node is either red or black. 2. Root Property: The root of the tree is always black. 3. Red Property: Red nodes cannot have red children (no two consecutive red nodes on any path). 4. Black Property: Every path from a node to its descendant null nodes (leaves) has the same number of black nodes. 5. Leaf Property: All leaves (NIL nodes) are black and do not store any data. They are placeholders used to maintain the tree structure. 3 Red-Black Trees vs AVL Tree  Most of the BST operations (e.g., search, max, min, insert, delete.. etc) take O(log n) time where log n is the height of the BST.  The cost of these operations may become O(n) for a skewed Binary tree. If we make sure that the height of the tree remains O(log n) after every insertion and deletion, then we can guarantee an upper bound of O(log n) for all these operations.  The height of a Red-Black tree is always O(log n) where n is the number of nodes in the tree.  The AVL trees are more balanced compared to Red-Black Trees, but they may cause more rotations during insertion and deletion.  So if your application involves frequent insertions and deletions, then Red-Black trees should be preferred.  And if the insertions and deletions are less frequent and search is a more frequent operation, then AVL tree should be preferred. 4 Operation: Insertion  Inserting a new node in a Red-Black Tree involves a two-step process: performing a standard binary search tree (BST) insertion, followed by fixing any violations of Red-Black properties. Step 1: Insert the new node with red color Step 2:  a) Node is root recolor it to black  b) [Red-Red violation] Case 1: Uncle is Red: Recolor the parent and uncle to black and the grandparent to red. Then move up the tree to check for further violations. Case 2: Uncle is Black or Null: Perform rotations to balance the tree. Recolor the nodes accordingly. 5 Example: Insertion 10, 20, 30, 15, 25, 5, 12, 35, 40, 32, 50 10 20 30 6 Example: Insertion 10, 20, 30, 15, 25, 5, 12, 35, 40, 32, 50 20 10 10 30 5 15 25 35 12 32 40 50 7 Example  Create red-black tree with following elements  8, 18, 5, 15, 17, 25, 40, 80  13, 3, 4, 12, 14, 10, 5, 1, 8, 2, 7, 9, 11, 6, 18 8 Deletion operation 1. Choose the node to be deleted as in BST 2. Perform the suitable case Case 1: if the node to be deleted is red, just delete it and exit Case 2: if DB is root, remove DB Case 3: if DB’s sibling is black and both nephews are also black (a) remove DB(if DB is null delete it, if DB is not null remove DB sign) (b) make sibling red (b) make DB’s parent black (if DB’s parent [ was black→ make it DB], if red → make it black), apply suitable case Delete 32 Delete 30 Delete 25 Delete 25 Case 1 Case 3 9  Deletion…continue  Case 4: if DB’s sibling is red Delete 15 ▪ Swap colors of DB’s parent and DB’s sibling ▪ Rotate parents in DB’s direction ▪ Reapply the suitable case Case 3 10  Deletion…continue  Case 5: if DB’s sibling is black, near nephew is red and far nephew is black, ▪ Swap color’s of DB’s sibling and DB’s near nephew ▪ Rotate DB’s sibling in the opposite direction of DB ▪ Apply case 6 Delete 1 Case 3 Case 6 ✓ Case 6: if DB’s sibling is black and far nephew is red ▪ Swap color of DB’s parent and DB’s sibling ▪ Rotate DB’s parent in DB’s direction ▪ Change color of red nephew to black ▪ Remove DB 11 Summary 12 https://www.cs.csubak.edu/~msarr/visualizations/RedBlack.html 13 Exercise  Delete 50, 20, 100, 90, 40, 60, 30, 10, 17, 80 14 Heap & Heap Sort Algorithm Introduction  A heap data structure is a binary tree with the following two properties. 1. It is a complete binary tree: Each level of the tree is completely filled, except possibly the bottom level. At this level it is filled from left to right. 2. It satisfies the heap order property: the data item stored in each node is greater than or equal to the data item stored in its children node. a a 9 9 b c b c 6 7 6 7 d e f d e f 2 4 8 2 4 1 Binary Tree but not a Heap Complete Binary Tree - Not a Heap Heap Heap 16 Array Representation of Heap  Heap can be implemented using an Array.  An array 𝐴 that represents a heap is an object with two attributes: 1. 𝑙𝑒𝑛𝑔𝑡ℎ[𝐴], which is the number of elements in the array, and 2. ℎ𝑒𝑎𝑝−𝑠𝑖𝑧𝑒[𝐴], the number of elements in the heap stored within array 𝐴 16 14 10 Array representation of heap 8 7 9 3 2 4 1 Heap 16 14 10 8 7 9 3 2 4 1 17 Array Representation of Heap  In the array 𝐴, that represents a heap 1. length[𝐴] = heap-size[𝐴] 2. For any node 𝒊 the parent node is 𝒊/𝟐 3. For any node 𝒊, its left child is 𝟐𝒊 and right child is 𝟐𝒊 +𝟏 𝟏 For node 𝑖 = 4, parent node is 4/2 = 2 16 𝟐 𝟑 For node 𝑖 = 4, 14 10 Left child node is 2 ∗ 4 = node 8 Right child is 2 ∗ 4 + 1 = node 9 𝟒 𝟓 𝟔 𝟕 8 7 9 3 𝟏 𝟐 𝟑 𝟒 𝟓 𝟔 𝟕 𝟖 𝟗 𝟏𝟎 𝟖 𝟗 𝟏𝟎 2 4 1 Heap 16 14 10 8 7 9 3 2 4 1 18 Types of Heap 1. Max-Heap − Where the value of the root node is 9 greater than or equal to either of its children. 6 7 2 4 1 1 2. Min-Heap − Where the value of the root node is less than or equal to either of its children. 2 4 6 7 9 19 Introduction to Heap Sort 1. Build the complete binary tree using given elements. 2. Create Max-heap to sort in ascending order. 3. Once the heap is created, swap the last node with the root node and delete the last node from the heap. 4. Repeat step 2 and 3 until the heap is empty. 20 Heap Sort – Example 1 Sort the following elements in Ascending order 4 10 3 5 1 Step 1 : Create Complete Binary Tree 4 1 2 3 4 5 4 10 3 5 1 10 3 Now, a binary tree is 5 1 created and we have to convert it into a Heap. 21 Heap Sort – Example 1 Sort the following elements in Ascending order 4 10 3 5 1 Step 2 : Create Max Heap 10 4 10 is greater than 4 1 2 3 4 5 So, swap 10 & 4 4 10 10 4 3 5 1 4 10 3 Swap In a Max Heap, parent node 5 1 is always greater than or equal to the child nodes. 22 Heap Sort – Example 1 Sort the following elements in Ascending order 4 10 3 5 1 Step 2 : Create Max Heap 10 5 is greater than 4 1 2 3 4 5 So, swap 5 & 4 10 54 3 45 1 5 4 3 Swap In a Max Heap, parent node 4 5 1 is always greater than or equal to the child nodes. Max Heap is created 23 Heap Sort – Example 1 Sort the following elements in Ascending order 4 10 3 5 1 Step 3 : Apply Heap Sort 1 10 1 2 3 4 5 10 1 5 3 4 1 10 5 3 Swap 1. Swap the first and the 4 10 1 last nodes and 2. Delete the last node. 24 Heap Sort – Example 1 Sort the following elements in Ascending order 4 10 3 5 1 Step 3 : Apply Heap Sort 5 1 Max Heap Property is 1 2 3 4 5 violated so, create a 15 451 3 41 10 Max Heap again. 4 1 5 3 Swap 1 4 25 Heap Sort – Example 1 Sort the following elements in Ascending order 4 10 3 5 1 Step 3 : Apply Heap Sort 1 5 Max Heap is created 1 2 3 4 5 51 4 3 15 10 4 3 Swap 1. Swap the first and the 5 1 last nodes and 2. Delete the last node. 26 Heap Sort – Example 1 Sort the following elements in Ascending order 4 10 3 5 1 Step 3 : Apply Heap Sort 3 14 Create Max Heap 1 2 3 4 5 again 14 3 41 43 5 10 Max Heap is created 1 4 34 Swap 1. Swap the first and the last nodes and 2. Delete the last node. 27 Heap Sort – Example 1 Sort the following elements in Ascending order 4 10 3 5 1 Step 3 : Apply Heap Sort 1 3 Already a Max Heap 1 2 3 4 5 3 1 13 4 5 10 3 1 Swap 1. Swap the first and the last nodes and 2. Delete the last node. 28 Heap Sort – Example 1 Sort the following elements in Ascending order 4 10 3 5 1 Step 3 : Apply Heap Sort 1 Already a Max Heap 1 2 3 4 5 1 3 4 5 10 Remove the last element from heap and the sorting is over. 29 Heap Sort – Example 2  Sort given element in ascending order using heap sort. 19, 7, 16, 1, 14, 17 19 14 7 16 17 1 7 16 14 17 Step 1: Create binary tree Step 2: Create Max- heap 19 19 7 16 14 7 17 16 1 14 17 1 14 7 16 17 30 Heap Sort – Example 2 Step 3 Step 4 19 16 14 17 1 7 16 19 17 16 14 17 16 1 7 19 16 19 17 16 Create Max-heap Swap & remove 14 17 the last 14 16 17 element 1 7 19 16 1 7 31 Heap Sort – Example 2 Step 5 Step 6 17 7 14 16 1 7 17 19 7 16 14 16 7 1 17 19 17 7 16 7 Create Max-heap Swap & remove 14 16 the last 14 7 16 element 1 17 7 1 32 Heap Sort – Example 2 Step 7 Step 8 16 1 14 7 1 16 17 19 1 14 14 1 7 16 17 19 16 1 1 14 Create Max-heap Swap & remove 14 7 the last 14 1 7 element 16 1 33 Heap Sort – Example 2 Step 9 Step 10 14 7 1 14 7 16 17 19 17 7 1 14 16 17 19 14 7 71 Already a Max-heap Swap & remove the Swap & remove the last last element element 1 14 7 7 1 Step 11 1 7 14 16 17 19 Remove the 1 The entire array is sorted last element now. 34 Exercises  Sort the following elements using Heap Sort Method. 1. 34, 18, 65, 32, 51, 21 2. 20, 50, 30, 75, 90, 65, 25, 10, 40  Sort the following elements in Descending order using Hear Sort Algorithm. 1. 65, 77, 5, 23, 32, 45, 99, 83, 69, 81 35 Heap Sort – Algorithm # Input: Array A # Output: Sorted array A Algorithm: Heap_Sort(A[1,…,n]) BUILD-MAX-HEAP(A) for i ← length[A] downto 2 do exchange A ↔ A[i] heap-size[A] ← heap-size[A] – 1 MAX-HEAPIFY(A, 1, n) 36 Heap Sort – Algorithm Algorithm: BUILD-MAX-HEAP(A) 4 1 3 2 9 7 heap-size[A] ← length[A] 1 4 for i ← ⌊length[A]/2⌋ downto 1 2 3 do MAX-HEAPIFY(A, i) 1 3 4 5 6 heap-size[A] = 6 2 9 7 4 1 7 2 9 3 4 9 7 2 1 3 9 4 7 2 1 3 i=3 1 i=2 1 i=1 1 4 4 49 2 3 2 3 2 3 1 37 91 7 9 4 7 4 5 6 4 5 6 4 5 6 2 9 73 2 91 3 2 1 3 37 Heap Sort – Algorithm # Input: Array A # Output: Sorted array A 39 4 7 2 1 93 1 Algorithm: Heap_Sort(A[1,…,n]) 9 BUILD-MAX-HEAP(A) 2 3 for i ← length[A] downto 2 4 7 do exchange A ↔ A[i] 4 5 6 heap-size[A] ← heap-size[A] – 1 2 1 3 MAX-HEAPIFY(A, 1, n) 38 Heap Sort – Algorithm Algorithm: Max-heapify(A, i, n) l ← LEFT(i) l ←2 1 3 4 7 2 1 9 r ← RIGHT(i) r ← 3 1 if l ≤ n and A[l] > A[i] 3 Yes 2 3 then largest ← l largest ← 2 4 7 else largest ← i 4 5 if r ≤ n and A[r] > A[largest] Yes 2 1 then largest ← r largest ← 3 if largest ≠ i Yes then exchange A[i] ↔ A[largest] MAX-HEAPIFY(A, largest, n) 39 Heap Sort – Algorithm # Input: Array A # Output: Sorted array A 3 4 7 2 1 9 1 Algorithm: Heap_Sort(A[1,…,n]) 7 BUILD-MAX-HEAP(A) 2 3 for i ← length[A] downto 2 4 3 do exchange A ↔ A[i] 4 5 heap-size[A] ← heap-size[A] – 1 2 1 MAX-HEAPIFY(A, 1, n) 40 Heap Sort Algorithm – Analysis # Input: Array A # Output: Sorted array A heap-size[A] ← length[A] for i ← ⌊length[A]/2⌋ downto 1 𝒏Τ𝟐 Algorithm: Heap_Sort(A[1,…,n]) do MAX-HEAPIFY(A, i) 𝐎( 𝒍𝒐𝒈 𝒏) BUILD-MAX-HEAP(A) 𝐎(𝒏 𝒍𝒐𝒈 𝒏) for i ← length[A] downto 2 𝒏−𝟏 do exchange A ↔ A[i] heap-size[A] ← heap-size[A] – 1 MAX-HEAPIFY(A, 1, n) 𝑶(𝒏 − 𝟏) (𝒍𝒐𝒈𝒏) Running time of heap sort algorithm is: 𝑶 𝒏 𝒍𝒐𝒈 𝒏 + 𝑶(𝐥𝐨𝐠 𝒏) 𝒏 − 𝟏 + 𝑶(𝒏 − 𝟏) = 𝑶(𝒏 𝐥𝐨𝐠 𝒏) 41 Binomial Heap Binomial Tree  A binomial heap is a collection of binomial trees.  Binomial tree Bk is an ordered tree defined recursively. The binomial tree B0 has one node. The binomial tree Bk consists of two binomial trees Bk-1 and they are connected such that the root of one tree is the leftmost child of the other.  Binomial tree properties:  Bk has 2k nodes  Bk has height k  For any binomial tree Bk , Number of nodes at depth i is given by binomial coefficient 𝑘! C(k,i) for i=0, 1, 2,…,k. {C(k,i)= } 𝑖!∗ 𝑘−𝑖 !  The root has degree k which is greater than other node in the tree. Each of the root’s child is the root of a subtree Bi. 43 Binomial Tree Example B0 B1 B2 B3 Depth i in B3​: 6 Depth 0: C(3,0) = 1 node (the root). 10 Depth 1: C(3,1) =3 nodes. 7 5 15 23 Depth 2: C(3,2) =3 nodes. 4 7 Depth 3: C(3,3) =1 node (the deepest leaf node). 20 15 8 10 11 6 25 B4 4 21 11 6 4 32 34 3 5 23 31 33 7 14 22 9 44 Binomial Heap Properties  Binomial heap(H) is a set of Binomial Trees.  Each binomial tree in H obeys the min heap property: key of a node is greater or equal to the key of its parent. The root has the smallest key in the tree.  There can be at most one Binomial Tree of any degree. {i.e. no two binomial tree of same degree}  The binomial trees in the binomial heap are arranged in increasing order of degree Example: head[H] 5 1 2 7 10 12 10 13 3 15 15 10 12 16 45 Binomial Heap Implementation  Each node has the following fields:  p: parent  child: leftmost child  sibling  Degree  Key (data)  Roots of the trees are connected using linked list. 46 Binomial Heap Implementation p a) c) key degree child sibling NIL NIL 2 1 0 2 head[H] NIL NIL b) 10 12 head[H] 2 1 1 0 NIL NIL 10 12 15 15 0 NIL NIL 47 Binomial Heap Operations  Create heap  Find minimum key  Union two binomial heap  Insert a node  Extract minimum node  Decrease a key  Delete a node 48 Create A New Binomial Heap  The operation simply creates a new pointer and sets it to NIL.  Pseudocode: Binomial-Heap-Create() 1 head[H]  NIL 2 return head[H]  Run time is θ(1). 49  Find Minimum Key  Since the binomial heap is a min-heap-order, the minimum key of each binomial tree must be at the root. This operation checks all the roots to find the minimum key.  Pseudocode: This implementation assumes that there are no keys with value ∞ Binomial-Heap-Minimum(H) 1 y  NIL 2 x  head[H] 3 min  ∞ 4 while x is not NIL 5 do if key[x] < min then 6 min  key[x] 7 yx 8 x  sibling[x] 9 return y  Run time: The run time is in the order of O(log n) since the most number of roots in binomial heap is |_(log n)_| +1 50 Find Minimum Key Example a) b) head[H] 2 5 1 head[H] 2 5 1 7 10 12 7 10 12 15 15 c) d) head[H] 2 5 1 head[H] 2 5 1 7 10 12 7 10 12 15 15 51 Union Two Binomial Heaps: Link Pseudocode: Binomial-Link(y,z) 1 p[y]  z 2 sibling[y]  child[z] 3 child[z]  y 4 degree[z]  degree[z] + 1  Example: link node 5 to node 1 5 1 1 7 12 5 12 child 7 sibling parent 52 Union Two Binomial Heaps: Merge  Binomial-Heap-Merge(H1,H2) 1. P  Head[H]; 2. P1  Head[H1]; 3. P2  Head[H2] 4. while P1 ≠ NIL OR P2 ≠ NIL do 5. if degree[P1] < degree[P2] then 6. sibling [P] P1; 7. P1  sibling[P1] 8. P  sibling[P] 9. else 10. sibling[P]  P2; 11. P2  sibling[P2] 12. P  sibling[p]  Run time: The running time is O (log n)  The total number of combined roots is at most |_logH1_| + |_logH2_| +2. Binomial-Heap-Merge is O (log n) + the while loop is O (log n). Thus, the total time is O(log n). 53 Union Two Binomial Heaps: Main Steps This operation consists of the following steps  Merge: Merge two binomial heaps. Merge the root lists of binomial heap H1 and H2. The resulting heap has the roots in increasing order of degree  Link: For each tree in the binomial heap H, link roots of equal degree until no same degree is there in H.  Case1: degree[x] ≠ degree[next-x]. The pointer move one position further in the list.  Case2: degree[x] = degree[next-x] = degree[sibling[next-x]]. Again pointer move one position further in the list.  Case3: degree[x] = degree[next-x] ≠ degree[sibling[next-x]] and key[x] = key[next-x]. We remove x from the root list and link it to next-x. 54 Union two Binomial Heap Binomial-Heap-Union(H1,H2) ▪ while next-x not NIL 1 H Make-Binomial-Heap() ▪ do if(degree[x] not degree[next-x]) or 2 Head[H]  Binomial-Merge(H1,H2) ▪ (sibling[next-x not NIL and degree[sibling[next-x]]=degree[x]) 3 Free the objects H1 and H2 but not the lists they point to ▪ then prev-x  x 4 If head[H] = NIL ▪ x  next-x 5 then return H ▪ else if key[x] key[x] 2. then error “new key is greater than current key” 3. key[x]  k 4. y  x 5. z  p[y] 6. while z not NIL and key[y] < key[z] 7. do exchange key[y] → key[z] 8. if y and z have satellite fields, exchange them, too. 9. yz 10. z  p[y] 64 Decreasing a key  Execution time: This procedure takes O(log n) since the maximum depth of x is |_log n_|. head[H] 5 2 head[H] 5 2 10 12 10 12 15 1 head[H] 5 2 head[H] 5 1 1 12 2 12 10 10 65 Delete a Node  With assumption that there is no node in H has a key of -∞.  The key of deleting node is first decreased to -∞.  This node is then deleted using extracting min procedure. Pseudocode: (from book) Binomial-Heap-Delete(H,x) 1 Binomial-Heap-Decrease-Key(H,x,-∞) 2 Binomial-Heap-Extract-Min(H)  Run time: O(log n) since the run time of both Binomial-Heap-Decrease-Key and Binomial- Heap-Extract-Min procedures are in order of O(log n). 66 Example a) b) head[H] 5 2 head[H] 5 2 10 12 -∞ 12 15 15 c) d) head[H] 5 -∞ head[H] 5 2 12 head[H’] 12 2 15 15 67  e) f) head[H] 5 12 2 head[H] 5 2 15 12 15 g) head[H] 2 5 15 12 68 Compare With Binary Heap Procedure Binomial Heap Binary Heap Make-Heap O (1) O (1) Insert O (log n) O (log n) Minimum O (log n) O (1) Extract-Min O (log n) O (log n) Union O (log n) O (n) Decrease-Key O (log n) O (log n) Delete O (log n) O (log n) 69 Fibonacci Heap Heaps are mainly used for implementing priority queue. We have discussed below heaps:  Binary Heap  Binomial Heap  In terms of Time Complexity, Fibonacci Heap beats both Binary and Binomial Heaps. 1) Find Min: Θ(1) [Same as both Binary and Binomial] 2) Delete Min: O(Log n) [Θ(Log n) in both Binary and Binomial] 3) Insert: Θ(1) [Θ(Log n) in Binary and Θ(1) in Binomial] 4) Decrease-Key: Θ(1) [Θ(Log n) in both Binary and Binomial] 5) Merge: Θ(1) [Θ(m Log n) or Θ(m+n) in Binary and Θ(Log n) in Binomial] 70 Priority Queues Performance Cost Summary 71  Find the union on the following 72  Original motivation: improve Dijkstra's shortest path algorithm from O(E log V ) to O(E + V log V ).  Basic idea.  Similar to binomial heaps, but less rigid structure.  Binomial heap: eagerly consolidate trees after each insert.  Fibonacci heap: lazily defer consolidation until next delete-min.  Fibonacci Heap is a collection of trees with min-heap or max-heap property. In Fibonacci Heap, trees can have any shape even all trees can be single nodes (This is unlike Binomial Heap where every tree has to be Binomial Tree). 73 Fibonacci Heaps: Structure Fibonacci heap.  It is a set of min heap-ordered trees. (i.e. The parent is always smaller than the children.)  Maintain pointer to minimum element.  Set of marked nodes(Decrease key operation)  The trees within a Fibonacci heap are unordered but rooted. 74 Memory Representation of the Nodes in a Fibonacci Heap  The roots of all the trees are linked together for faster access. The child nodes of a parent node are connected to each other through a circular doubly linked list as shown below.  In Fibonacci heap, each tree of degree n has atleast Fn+2 nodes in it.{}  There are two main advantages of using a circular doubly linked list.  Deleting a node from the tree takes O(1) time.  The concatenation of two such lists takes O(1) time. p key degree L-sibling R-sibling mark Any child Mark(18) = 1 (lost one of its children) Mark(38) = 0 (lost no chilld) 75 Fibonacci Heaps: Structure Fibonacci heap.  It is a set of min heap-ordered trees. (i.e. The parent is always smaller than the children.)  Maintain pointer to minimum element. (find-min takes O(1) time)  Set of marked nodes(Decrease key operation)  The trees within a Fibonacci heap are unordered but rooted. 76 Fibonacci Heaps: Structure Fibonacci heap.  It is a set of min heap-ordered trees. (i.e. The parent is always smaller than the children.)  Maintain pointer to minimum element.  Set of marked nodes(Decrease key operation)  The trees within a Fibonacci heap are unordered but rooted. 77 Fibonacci heap: Notations  Notation.  n = number of nodes in heap.  rank(x) or degree(x) = number of children of node x.  rank(H) = max rank of any node in heap H.  trees(H) = number of trees in heap H.  marks(H) = number of marked nodes in heap H 78 Fibonacci heap operation  Insert  Link  Delete min  Decrease Key  Union  Delete 79 1. Fibonacci Heaps: Insert  Insert.  Create a new singleton tree.  Add to root list(left child of min[h]); update min pointer (if necessary). 80 Insert => O(1)  Insert.  Create a new singleton tree.  Add to root list (left child of min[h]); update min pointer (if necessary). 81 2. Fibonacci Heap: Linking Operation Linking operation: Make larger root be a child of smaller root. 82 3. Fibonacci Heaps: Delete Min Delete min.  Delete min; meld its children into root list; update min.  Consolidate trees so that no two roots have same rank. 83 Delete Min Delete min.  Delete min; meld its children into root list; update min.  Consolidate trees so that no two roots have same rank. 84 Delete Min Delete min.  Delete min; meld its children into root list; update min.  Consolidate trees so that no two roots have same rank. 85 4. Fibonacci Heaps: Decrease Key  Intuition for deceasing the key of node x.  If heap-order is not violated, just decrease the key of x.  Otherwise, cut tree rooted at x and meld into root list.  To keep trees flat: as soon as a node has its second child cut, cut it off and meld into root list (and unmark it). 86 Decrease Key Case 1. [heap order not violated]  Decrease key of x.  Change heap min pointer (if necessary). 87 Decrease Key Case 2a. [heap order violated]  Decrease key of x.  Cut tree rooted at x, meld into root list, and unmark.  If parent p of x is unmarked (hasn't yet lost a child), mark it;  Otherwise, cut p, meld into root list, and unmark (and do so recursively for all ancestors that lose a second child) 88 Decrease Key Case 2a. [heap order violated]  Decrease key of x.  Cut tree rooted at x, meld into root list, and unmark.  If parent p of x is unmarked (hasn't yet lost a child), mark it;  Otherwise, cut p, meld into root list, and unmark (and do so recursively for all ancestors that lose a second child) 89 Decrease Key Case 2a. [heap order violated]  Decrease key of x.  Cut tree rooted at x, meld into root list, and unmark.  If parent p of x is unmarked (hasn't yet lost a child), mark it;  Otherwise, cut p, meld into root list, and unmark (and do so recursively for all ancestors that lose a second child) 90 Decrease Key Case 2b. [heap order violated]  Decrease key of x.  Cut tree rooted at x, meld into root list, and unmark.  If parent p of x is unmarked (hasn't yet lost a child), mark it; Otherwise, cut p, meld into root list, and unmark (and do so recursively for all ancestors that lose a second child). 91 Decrease Key Case 2b. [heap order violated]  Decrease key of x.  Cut tree rooted at x, meld into root list, and unmark.  If parent p of x is unmarked (hasn't yet lost a child), mark it; Otherwise, cut p, meld into root list, and unmark (and do so recursively for all ancestors that lose a second child). 92 Decrease Key Case 2b. [heap order violated]  Decrease key of x.  Cut tree rooted at x, meld into root list, and unmark.  If parent p of x is unmarked (hasn't yet lost a child), mark it; Otherwise, cut p, meld into root list, and unmark (and do so recursively for all ancestors that lose a second child). 93 5. Fibonacci Heaps: Union  Union Combine two Fibonacci heaps. 94 6. Fibonacci Heaps: Delete Delete node x.  decrease-key of x to ∞  delete-min element in heap. 95 Exercise Create Fibonacci-heap for the following lists: L =. And perform delete min and decrease the value 30 to 13.  https://www.cs.usfca.edu/~galles/JavascriptVisual/release1.2/FibonacciHeap.html 96 Disjoint set data structure  What is a Disjoint set data structure?  Two sets are called disjoint sets if they don’t have any element in common, the intersection of sets is a null set 97 Disjoint set data structure Consider a situation with a number of persons and the following tasks to be performed on them: Add a new friendship relation, i.e. a person x becomes the friend of another person y i.e adding new element to a set. Find whether individual x is a friend of individual y (direct or indirect friend) We are given 10 individuals say, a, b, c, d, e, f, g, h, i, j Following are relationships to be added:  a b , b d , c f, c I, j e, g j Given queries like whether a is a friend of d or not. We basically need to create following 4 groups and maintain a quickly accessible connection among group items:  G1 = {a, b, d}  G2 = {c, f, i}  G3 = {e, g, j}  G4 = {h} 98  Find whether x and y belong to the same group or not, i.e. to find if x and y are direct/indirect friends.  Partitioning the individuals into different sets according to the groups in which they fall. This method is known as a Disjoint set Union which maintains a collection of Disjoint sets and each set is represented by one of its members.  To answer the above question two key points to be considered are:  How to Resolve sets? Initially, all elements belong to different sets. After working on the given relations, we select a member as a representative. There can be many ways to select a representative, a simple one is to select with the biggest index.  Check if 2 persons are in the same group? If representatives of two individuals are the same, then they’ll become friends. 99 A disjoint–set is a data structure that keeps track of a set of elements partitioned into several disjoint (non-overlapping) subsets. Operations on Disjoint set are:  Find: It determines in which subset a particular element is in and returns the representative of that particular set. An item from this set typically acts as a “representative” of the set.  Union: It merges two different subsets into a single subset, and the representative of one set becomes representative of another.  The disjoint–set also supports one other important operation called MakeSet, which creates a set containing only a given element in it. 100 How to Implement Disjoint Sets?  Disjoint–set forests are data structures where each set is represented by a tree data in which each node holds a reference to its parent and the representative of each set is the root of that set’s tree.  Find follows parent nodes until it reaches the root.  Union combines two trees into one by attaching one tree’s root into the root of the other. 101 Example For example, consider five disjoint sets S1, S2, S3, S4, and S5 represented by a tree. Each set initially contains only one element each, so their parent pointer points to itself or NULL.  S1 = {1}, S2 ={2}, S3 = {3}, S4 ={4} and S5 = {5}  The Find operation on element i will return representative of Si, where 1