A&DS S01E09. Fibonacci Heap

0:00 [Music] so today we'll talk about female ships oh let's go so what is the fibonacci hip is a hip so it is data structure which supports operation like add element and remove minimal elements

0:50 uh like normal but like normal binary heap which we discussed on the second lecture these two operations are the common operations for all heaps it also supports some other different operations ah it also supports two important operations first important operation is to merge to hips they are merged like in uh like in design sets so you have two two separate heaps uh and you like unite the set of all

1:35 elements like you have one big hip which contains all elements of both hips and the final operation is to decrease the key this separation basically takes some element which is already in the heap and change the key of this element to some another key so we take some element x and change the key to y so what happens we have the element in the byte in the heap somewhere so some element x

2:22 that's a spoiler this direction will usually look something like that uh so we take this element so we have like a pointer to this element so we have pointer to this element x and you change this element x with y and you can do it only when y is less than x y should be less than x so this is the operation decrease key we take some element which is already in the hip and decrease the key of the cell that's all that's all we want to do today

3:09 looks not that hard right um at first let's talk about what we already learned we already know how to how to make binary heaps right uh if you use binary heap then you can add element in logarithmic time uh you can remove medium in log on time you can decrease the key in log and time just decrease the key and then sift the element up so you can decrease the key in log in time uh you can't merge to binary heaps easily but you actually can do it like if you think about it when you

3:55 when you do something like uh like we did with the disjoint sets so if you merge to hip just by inserting all elements of the smaller hip to the bigger hip then you will take something like log square but it's not not no it's widely used so most commonly binary heap supports these three operations and they all work in log in time share some code i i will i don't think i will write a code of fibonacci heaps because it's it's not supposed to be implemented yeah no i i think it can be implemented

4:42 pretty easy so it's the code will not be hard so but it's just not effective enough because the constant factor will be too big so it's not usable in most problems but i think it can be implemented pretty easily the code is pretty simple all right i'll look at it later a little bit later now first before we learn what what is fibonacci hip and how to make fibonacci we will run some simpler heap which is binomial

5:33 is just eat something like fibonacci hips like first step before we reach the fibonacci heap it's just easier to understand but your hips be when you already know how how binomial hips work so here we go what hip is the hip which is built on top on a phenomenal trees so uh the simple heap we discussed on the second lecture is based on binary trees each node has exactly two children and the number of three is something different a binomial trees looks like

6:18 this uh rapid announcements of different ranks so uh minimum things for bring zero is just one vertex so this is the phenomenal tree of rank zero uh an ml3 of rank one uh there's just two vertices one note and another note here looks very simple right now let's see video copy of rank 2 now it gets a little bit a little bit more complicated to have something like that and two more

7:06 vertices here and when the multiple frame three looks like this we have vertex and we have one vertex here two vertices here and another four vertices here and so on so the binomial tree of rank k looks like cheese so if we have pk looks like this uh you have you have the vertex the root of the tree has exactly k children

7:51 ah the first child is just one vertex second child is two vertices then we have uh three uh three like this okay right three here we have three b two here we have three b three and so on the last three is b k minus one so we just take all the previous trees combine them and build one vertex one this is how binomial trees are constructed so each hbmo3 each negative you can

8:37 stuck it off all previous animal trees combined by one common root okay uh there is another way of thinking about minimal trees is the following you can think of either or with binomial 3 of rank k like this so the number of ranking is constructed by taking binomial 3 of rank k minus 1 and adding another child here which is also a binomial trio thing i mean this one so that that's another way of thinking about binomial trio frame k so again it is this is this the same

9:25 scheme so so he here here you have benoit and k minus one it means that you have a root and the children have ranks from 0 to k minus 2 and here you add another 3 of k minus 1. so you have all trees from 0 to k minus 2 and another of k minus 1. so you have all threes from 0 to k minus 1. is it clear now it doesn't you're too quiet again just if everything is clear just say everything is clear so i will stop and go to the next ah now let's be the milk crease now what we need is to build heap on top of this trees

10:11 and how to build a hip from a tree no it's simple you just take some tree and uh make the hip invariant like we did in the vital tips for example we can take this tree and put the put the elements in each node of this tree for example here we may take this tree and add some elements take something like that and add some numbers here like here one five three six eight three

11:01 nine ten and twenty five that's the heap which is built on top of the l3 so uh we maintain the following property that the element each element is less or equal than the its children this elements let's look at this let's recall this that's how we will construct our minimal heap now what is uh

11:46 if we can use only this freeze what is the number of elements we can make so what is the number of nodes in the binomial trio prank k now you can see that a binomial three or friend zero have one node these have two nodes these heads four nodes this has eight nodes and so on so uh the minimal tree of ram k contains exactly two power k nodes good so if you want to put exactly two power k elements in

12:33 your binary in your opinional hip that's fine you just take the tree open k and build hip like this uh what if the number of element is not the power of two for example what if you want to put like say 11 elements in your binomial so if you have 11 elements and you want to build a binomial heap of these 11 elements what can you do you take not one tree but several tricks so you you take this three o'clock k operand three and put eight elements here now three elements left so you take another uh tree of rank one

13:20 and put another two elements here uh now we have four eight elements here two elements here it's ten one more so we need another three of rank zero so add another three opening zero that's all that's how we support that by binomial heap of eleven elements so let's add some elements here so we have two and seven here and some 17 here so that's the correct binary heap where the normal heap of 11 elements

14:09 this is the minimum heap it will always look like like lightning again what we want to do we want to make several binomial trees and the total number of elements in this trees should be n uh to make it fast we want the number of these trees to be minimal possible how can we uh what what is the minimal possible number of trees we can take so that the total number of element is m

14:58 that's quite easy ah because we we cannot add elements we want we use several trees because we want only the trees of this fixed structure we want we we want to use only the trees like this and do not uh the structure of the tree is fixed so you can just add one more element to this tree it will be not the correct binomial tree so we want we want to construct uh the heap only from binomial 3 so we only want to use trees like that and because the number of elements is always 2 in power of k then sometimes we need several trees so if we have 11 element

15:44 we need several trees because the size of each tree is the power of two so we need to split this 11 in eight plus two plus one and put eight elements here two elements here and one element here what is the advantage is good question we will have tree then it the advantage will show what are the ones but once they could easily merge these trees actually we'll talk about it just in a minute

16:31 we'll talk about the advantages in again what i want to do i want to take the minimal possible number of trees uh let's see without i wha what what what can be the minimal possible number of trees uh the minimal most possible number of trees will be about look at uh because how can i how can i split this n in logan summons like this i take the biggest possible power of two uh subtract it from n i will get the number at least twice less than n then i take another biggest possible

17:18 power of 2 subtract it from n and so on so the number of trees if if each time i take the maximal possible power of 2 then ah that took us two to two consequences first all ranks of this three will be different oh because if i take two threes of the same rank it means that i can take the one three of the next round instead so if for example i take

18:03 two threes off and apparent one it means i take two vertices plus another two vertices instead of this i can take just this three so the total number of trees will be less so if i take the minimal possible number of trees then all trees must have the different rank and the second consequence is that ah all rings i not more than logarithm uh all the rings are not more logarithmic it means that the number of trees is atmosphere

18:57 is it clear enough again ah why all ramps are different because if you have two trees of the same rank it means that you use like two vertices and another terms instead of doing this you can take just one three operand k plus one and put this vertices in this bigger tray so if you want to minimize the total number of trees you always keep all all ranks of all trees different uh and the second is because all ranks are at most uh log n because 3 of ram k contains 2 power of k elements this k shouldn't be more than logarithmic of n and if all ranks are different and ranks

19:42 are no more than logarithm then the number of trees is atmospheric cool that's all that's the binomial heap now let's implement all operations so ah all operations in by binomial heap work in logan time so i will just implement all these operations in all in logan time uh let's start from the perspiration let's add one more element to the binomial heap how to add one more element

20:28 let's just add one element right here right here so suppose you have one more element if you want to add it to the binomial heap let's say element four this is element four and i want to add this element to this binomial heat first one element is the binomial tree of rank zero so let's just think about this one element as a small tree of random zero like this so this is three of zero let's try to

21:15 add these three or from zero to our binomial heap if in our binomial heap there is no three or front zero then we just add this one more element to the binomial heap like in one individual tree and and it's done and if we have the tree of rank one then what can we do we can merge these two trees so so again we have this three open one we look on this minimal tree in our binomial heap if we also have the rank one then we merge this two trees in one big tree so how to merge these two trees in one big tree or front one we look on the roots of these trees

22:02 take the minimal root and put another root as a child of this root so we take this 17 remove it from here and add it as a child of this now we have the tree of rank one so this is the 3d one this now we do the same we try to add this feed three in our binary heap if we already have the tree or frank one like this then what can we do we can merge these two trees so we can take our tree take these three and combine them to make the tree of rank two how to combine these trees we look on

22:49 the to these two root elements the smallest element is true and put another tree as the child of this root element so we take this four and add it here and now we have the trio friends too we check if we have another frame two we don't have another three or frank two these three have rank uh two and these three have ranked three now all the trees have different ranks so we have the correct binary heap

23:35 well here that's all that's how you add elements to the binomial heap again you add element as the tree of rank zero if you already have three frames zero then you combine this piece and like fuse them together and get the tree of rent one if you have another frame pawn you again you combine them and make it through your friends two and so on until you have the tree which uh which is unique if you don't have another tree of the same red then you just put these three in your binomial heap and you have the correct binomial here that's all again if you have a skill just say atmosphere i will repeat i think until you say something

24:24 uh yes we will we'll get emerging in a minute yeah what is the time complexity what are the differences i will show the time complexity and then we will go to merchant uh what is the time complexity uh how can we combine two trees in into one so let's see so if you have two trees of rank k so we have one tree or represent k another tree frank and you won't merge them in into one tree of rank k plus one i claim that i can do this in constant time so how to merge two trees into one big

25:12 screen uh it's quite simple you look on the root elements so you take these two root elements say x and y check which root is smaller for example if x is less than y ah then here then you take the smallest root and add another child to x uh if you want to be able to do this in constant time you need some data structure uh which contains the children of each node in such a way that it's easier to add one more element to this

25:57 list of children and the most easy way to do this is just use linked lists like we did so what you can do is to maintain your children as a linked list um you're right i'll write right here so you support linked list like this i will make i'll make the directional list and you make the link yes if you want to add the element to the end of this list you need

26:43 the link to the ad and you need the link in my let's have a link to both first and last element i'm not sure which one it's uncollected and the same way here so to to maintain the list of the children you just make the linked list you make linked list of all children here you make the linked list of all children here

27:29 and here you have only one child let's have two pointers so that's how you maintain the structure of your tree so in each node you have the linked list of its children you are just like like you have the pointer to the first element to the last content of this list and let's say you have the directional link listed here i think some pointers may be removed but i'm not sure which one so i just stay older i think it's enough to have pointer to the last element and pointer to the previous element in the list so

28:18 yeah it's good enough it's it's this theoretical lecture if you want to to to implement this you i think you can remove some pointers they are not used but good enough no we will not implement manage heaps today i think by the end of this lecture it should be clear enough how to implement fibonacci heaps but it's not it's not hard to implement this it's just not not you don't need to implement here because they are slower than the usual hips usually in most problems what i was talking about ah so if you maintain your trees like this then you can add this white to this tree in constant

29:05 time so if you want to add this list this element here you just have this pointer from x so you have pointers to the first and the last element of this list so you just take this last element do you see that's the point of this last element add this y to this list and move this pointer here so you do it in constant number of pointer machine operations the total number of operations here is constant now let's look how we add element when

29:50 we add one element to the binomial heap then we first we add element as a tree of frank zero then each time we combine two trees and get the tree of the bigger rank so first we add one three or friend zero we then combine and take get the tree of rank one then we come by and get the tree of rank two and so on so each time we combine two trees we increase the rank of the current tree and all ramps are not greater than logarithm so total number of these merging two trees will be at most logarithmic so the total time or complexity of this add operation is logan

30:37 all operations will be moving okay that's how you add one more element to the binomial heap and login time good let's go next uh let's talk about merkel a merging two binomial hips is actually quite the same as adding one more element so actually adding one more element is actually merging one hip with the hip of a single element so uh uh uh i need to clear something let's clear this i don't need this

31:30 anymore let's roll version how to merge how to merge two binomial hips ah pretty much the same like we did when we merge two sorted arrays so you maintain each binomial heap as the list of trees and you keep this list in sorted orders by the ranks of the three uh oh for example let's say let's say we have one tree of friend again of 11 elements like here so we have

32:17 three operand three like this uh another tree of friend one and another tree of friend zero like this and we have another keep this one and we have another heap let's say let's say we have three operand two three operand one and another three of frank zero markets this is heap two and we want to merge these two trees into one big tree one level two these two hips in one into one big hip so uh we do it pretty much the same as

33:03 we did when we merge two sorted arrays so each time you take two minimal each time you take two minimal elements so we take two trees of minimal size so you take these three and these three take the minimal of these trees and put this tree in the resulting tree in in the resulting binary heap here uh we here we have the three operandic zero and here we have another tree of frame zero we don't want to have two trees of the

33:49 same rank in the resulting binary binomial hip so what can we do we can just combine these trees into one big screen so we take these two trees of frank zero uh remove them from their hips then merge them into one tree of french one and put these three or frank one in the result yeah frank one go friend one one one one one one okay we have we have these two pointers to do the minimal three in each by in each binomial hip so we take these two elements up to two trees check if the rank is the same

34:36 then we want to combine this three in into one tree or rank one and put these three open clock in in the resulting and so on then we move to the next here we have trio frame one here we have three of rank one the interesting fact that here we have an output rank one so we may have uh three three trees of the same rank at some point so we may have one three here one three here and another three here and these three trees will have the same ranks this might happen so what we do when we have three trees for the same uh we combine

35:22 these two into one tree of rank two and leave this three here so we take these two trees and then remove them combine them into three o'clock two and that's all now in the resulting hip all the trees have the different ranks that's what that's what we try to achieve oh let's move to the next we have three here now here we have trees of different ranks so we take the minimum size strip and try to put it in our resulting binomial heap now we see that

36:10 these three have the same rank as these three now these two trees have the same rank we don't want to have the trees of the same rank so when we see two trees of the same rank we just merge them so we take these three take these three merge them together and get the tree of friendly and that's almost all now now we take these three look in this tree have the trees of the same rank so let's remove this merge them together have the three operator info that's all in the end you have this binary binomial heap uh here all trees have different ranks

36:56 and it contains all the elements from both these hips that's all that's how how you merge to pin binomial actually hips code is quite easy if you want to implement this it's quite easy it's basically the same as the code of emergency erase but a little bit more complicated so also but here sometimes when you actually you can do it the same way as you do version two arrays you can just merge this to erase into one degree and then do all the merging of these trees of equal size you can do it in this way so you can first you can merge these two lists into one big list with some trees of equal rank and then in another uh uh step you just iterate

37:43 all trees and if you see two trees of the same branch you just merge them you can do it like this it's always possible says as you wish ah that's all that's how you merge to binomial heaps uh what is the time complexity uh again uh like like in certain emerging sorting arrays uh here we have we make a linear number of operations when you merge two arrays you you have a linear number of predictions each time you take either one element from here or one two so total number of these operations will be linear and total number of merging two trees will be linear because we have linear it's here linear here so total will be linear so it's linear from the number of trees so number of trees in both hips it is at

38:29 most logarithm of n so this time complexity is linear from this number of trees so it's a logarithmic i think it's clear enough right so uh the time complexity of this margin is cool that's almost all uh now how to remove the minimal element so imagine you want to remove the minimal element from your binary heap uh let's use this binary heap imagine you use this binomial heap and you want to remove the minimal element

39:14 now first let's find the minimal element female elements here now let's remove this element so we get take this element and remove it from the binomial here what will be left uh we will need to take care of its children so after we remove this element we have these children elements and we want we need to do something about it so what can we do we can take all the children of this removed minimal element yes minimal element is always the root of the sun tree it's quite obvious yeah right

39:59 so minimal element is always the root of some tree is it obvious right i think it is so uh we remove this root of this tree so we take the children of this removed element and now we try to put these elements back in the in the binomial hip how can we do it ah it's quite easy so we take this element this uh these children of this removed root are the binomial trees of different ranks because all uh i ordered this so all children of of the root elements are binomial trees of different ranks just by definition of binomial trees so

40:45 these trees are all binomial trees of different ranks so we can combine them in one binomial heap we can say that this is binomial heap h2 and this is binomial keep h1 and then we just pull the merch operation to combine what get left of the binomial heap after we remove this minimal element and this hip containing of children of the removed element uh that's all we just combined these two hips using this merge procedure and we get the heap which contains all the elements except this one removed element

41:31 that's all that's how you remove the minimal element ah in the end you need to find another minimum yes after you merge these two hips into one you need to find next minimal element this can be done just minimal element is the root of some tree so you just iterate or all roots there are at most logarithmic number of roots so you just iterate all logarithm rules and find the new minimal element that's all that's how you remove cool that's almost all uh the way you talk about decrease key let's let's let's talk about but the chris key is not no not that interesting in binomial heap

42:19 in binomial heap when you decrease the key you can just uh do the same as we did in the binary heap just decrease the gain shift it up if you want to do it in logarithmic time the the height of the tree is at most logarithm so you can do it in the same way as we did in the binary heap so you decrease the key and then seep the element up to the root it will take logarithmic number operations so chris key is not very interesting here that's all that's how binomial keeps our working that's half a lecture cool

43:05 now we'll move to the fibonacci tips finally uh the plan is to do basically the same but slightly harder so so we will try to improve everything to make it even faster uh what is the plan let's let's go to the plan so what is the plan the plan is to have some operations work faster than logarithmic time actually working constant time ah first of all we need to we want to have ad iteration actually in binomial heaps addition

43:51 already works on constant time we'll discuss it in the practice next week but it it is actually all it is already satisfied we just didn't talk about this uh now we want to be able to merge the hips in closer time that's something less fruitful well but it's possible we can merge two fibonacci hips in constant time just take one hip take another hip boom you have a big hip in constant time perfect data structure and finally we want to have decreased key decrease key also working constantly uh that's kind of strange why i why i care so much about decreased key

44:37 operation it's actually quite important uh in some problems which we will discuss next year when we will discuss uh dx algorithm uh prim algorithm and stuff like this uh in some graph algorithms sometimes you need a operation like this so basically it happens in situations like this so you have some you have some groups of elements like indexer you have like the set of edges for each for each vertex you have set of edges that doesn't matter we'll discuss next here it's just a teaser

45:22 so ah you have groups of elements and for each element you have the minimum you have minimum in each group and in what you want to do in the extra for example is to take the minimal group so we group which contains the minimum possible element and take this group and remove it completely from the hip so you want to take this group and remove all the group from the from the hip and the way you do this is just by maintaining each group as the single element in the in the hip ah so so why why do you need a grease key because when you add more elements in your heap you add one element to this group

46:08 the minimum is always decreasing so if you have some set and you add more elements to this set the minimum is only decreasing so the direction you need in the disk for example is to decrease the current key of the element so you have some group of in in your binary heap in your fibonacci and you want to some update this group and when you update the group the minimum was always decreasing so you need version decrease here you you never want to increase the key well you only need to decrease the key that's we'll discuss next year so it's important in some ins in some important problems of graph theory uh yeah that's a good point uh this

46:54 complexity is not exactly exactly constant this complexity is amortized so all these complexities are amortized now we will discuss what is the mortise cost image cost means that you if you have some number of operations then the sum of time complexities of all the separations will be no more than and so on it's not no it's not the worst course not the basis it's it's the worst case amortized time no it's always we always talk about worst case separations it's the worst case amortized time

47:42 um and finally this remove minimum uh unfortunately we cannot make all operations in logarithm time that's quite obvious but it's unfortunate but it was it was not expected uh so this final operation will work in logan oh we need at least one operation to work in logan time obviously um no amortized mean again you can you can reverse lecture about martin's time amortized means that if you have this series of operations then the sum of times of these operations will be no more than the time of this amortized cost we sorry i don't have much time to

48:28 discuss about nice those costly okay we have much stuff to do you can do watch lecture we have a nice lecture about amortized course and stuff like this so let's go i think it will be quite clear what i mean about high school very soon

49:14 uh exercises let's go let's start from the symbol operations let's start from adding one more element to technology imagine you have standard by binomial hip imagine keep like this last time we tried to make the minimal possible number of trees so we say that we all trees in our banana heap have different ranks let's remove this property let's uh

50:01 say it's okay to have trees of the same rank it's fine so we might have these three of and two at 0.0 and another let's read it now 3 and so let's say that that is an ice cube so if you remove the property that you all the trees must have different ranks then how to add one more element to the screen very simple you just create one three o'clock zero and add this tree to your binary people to your fibonacci push

50:49 that's all that's how you add one more element to your fibonacci hips heaps very simple instruction cool now how to merge to fibonacci hips how to merge the fibonacci imagine you have two different fibonacci tips like one fibonacci heap and another again if you don't want all the trees have different ranks then you can just concatenate these two lists

51:35 so if you maintain each fibonacci heap as the linked list of all these trees then you can just concatenate these two lists that's all that's how you merge to fibonacci hips in constant time is that cool uh and now finally we need to pay for this because uh this all was very very very very interesting very cool but at some point we will need to pay

52:22 uh when we need to pay uh when we need to remove the minimal level uh so what happens when you remove the minimum element first how to find the minimal element let's have a point of the minimal element so let's have a point of the minimal element so each time we have a point of the minimal element when you add one more element you just check if this element is less than minimum then update the minimum when you merge to hips you have minimal element here minimal element here you check which of these two element is minimal and then then saying that this element is new so each time you have the point of the minimal element in your fibonacci heap

53:07 that's simple so when you need to remove minimal elements what you do okay so we have this let's have some big or something here something here so imagine you have this this element is minimum and you have some other trees here and so on so so this is mimo element yes that's true if you if you add elements one by one then you will have uh the array of

53:54 elements of rank 1 that's that's absolutely true if you just want if you just add n elements one by one you will have the list of single elements that's true but we will think about it later uh the the idea behind all these amortized structures sounds like this if you need to do something do it when you need it so uh at some point we will need to do something so we will just shift this time to the point when we need it at least just just in a minute so here what happens when you remove the minimal element so this is the minimal element you remove it from the from your hypnotic hips you remove the settlement from the humanitarian heaps uh what you have left you have left all

54:41 its children yeah so what you can do is just add all these children single crease so you take all these elements and add them here one by ones just add these all this elements here again how to remove the minimal element we have the link to the minimal element we take this minimal element now take all its children all children

55:29 are good trees so we take all these children and move them to this route now we have some more trees in our fibonacci heap spot it's fine now where's the problem i can do this all pretty fast i can just take all these children remove them add them to the fibonacci heaps i can do it in constant time basically like if i maintain the list of children as linked list i just i can just concatenate these two lists and do it in constant time but where's the problem

56:16 uh yes at some point we need to make a good treat yes that's true but but why do we need it looks like we are fine we can merge we can add we can remove minimal element oh the problem is pretty simple after you remove the minimal element you need to find the next minimal element because we had linked to this minimal element we remove it now we need to have a link to the next minimal element and how to find minimal element in this mess it's not that easy because if you add elements one by one then indeed yeah right you have the array of elements and you cannot find the next minimum quest

57:02 to find the next minimum you need to check all the roots of all the trees and you may have up to entries at this point so this is not the you you just cannot do it fast what we'll do we will try to again we need to spend some time to find the next minimal element let's try to use this time to up to two huh yes right ah so what i was talking about yeah i forgot what i was talking about

57:48 yeah so we need to spend some time to find the next minimal l uh and let's try to use this time to do something available so let's try to use this time to modify out our financial hip to make it more balanced let's idea what we'll do imagine you remove this minimal element take this element put it in here and so on so and then you have some fibonacci heap which is not balanced at all so you have after you remove the minimal element and so on you end up with something like this so you have you have some string fibonacci heap where is

58:34 very unbalanced uh one more and another element here and so on you might need to end up with something like this so this is your fibonacci keep at this point and you need to find the minimal element uh what you do you just iterate or all roots of whole trees and at the same time try and try to balance it how to balance fibonacci tips very easily let's create an array of logan elements and try to merge the trees of the same run like like before

59:19 so what we try to do is to iterate our old all routes and it at the same time uh make all trees have different ranks so we go from left to right and just maintain for each round maintain the pointer to the three of this ring so we start from kiso here we have three operand one so we put the pointer from here to this tree now we have the tree of rank two so we take the pointer from here to this tree so it's pointer two two two two there uh now we have another two frame one

1:00:08 now we check we already have three frank one huh that's not good we will make merge these two trees so let's merge these two threes let's take these three let's see take another tree of rank one merge them together like this and get the trio frank too now we take this three rank two and try to add this three of uh we remove this now we take this three or frank two and try to add it in our array

1:00:54 but we already have three ring two so we merge them together [Music] and have a 2.3 okay yeah it's it's kind of laser effect restriction so it's like you have bad data structure but when you need it to be good you just only at the point when you need it to be good you make this restriction yeah and so on now you go to the next element so here you have three offering three now here we have three operand zero here we have an outline of rank zero you combine them

1:01:42 make it through frank one now we have another two franc one here again you combine them and that's all so in the end of this cleanup you have all all the trees have different ranks that's all so again how you remove the minimal element first you take the minimal element take all those children add them to the to your fibonacci hips now you have a big number of trees in your fibonacci hips you make this cleanup procedure just go

1:02:28 from all iterator all your roofs of all the trees and try to make them all have different ranks if you have two trees of the same rank you combine and have three of one more rank and so on in the end you end up something like this uh this this is the end state of which heaps up to this clean up in this tree you have no more than logan tricks here we have no more than log entries so we just in the end we just can iterate all the roots and find the minimum just just maybe just generate all rules and find the next minimum

1:03:16 okay now what is the time complexity of this cleanup uh let's see if you have let's try so so in the end you have three like this one so imagine you have m trees in your fibonacci hips this is before so what happens after your you clean up all the trees and help make all trees have different breaks you well you'll have some small number of trees you will have login trees in your in your relationships

1:04:02 uh so what we need to do to prove that the amortized cost is small we need to find some potential function which is decreased when we go from here to here let's remember what is what is the amortized cost matrix cost is the sum of cost plus change of the potential so this this is the real time of the separation uh in our case it is m we just need to iterate of all trees in our financial heap and so if we want this amortized cost to be log n

1:04:47 we need to have a potential function which is about minus m yeah just to compensate this m so we need to choose the potential function in such a way that it is decreased when we go from this state to this state any ideas again how the amortized cost works we make some potential function like this like this fee

1:05:33 and we when we increase the potential function we think that we spend more time and when we when we decrease the financial function we say that we spend less time so when we have some long operation we want this uh potential to be to decrease at least by the same value as the extra time we spent so here we spend extra m time and we don't want the time complex to be m so we need to have the potential such that the change of the potential from this state to this state is about minus m just to compensate this plasma any ideas about huh

1:06:18 number of trees right fine so the potential function in this case is just the number of trees in your fibonacci heaps good so what is the change of potential from this state to this thing here we have entries here we have log entries so change of pattern of potential is log n minus m so this delta v is log n minus m so the amount is cost will be m plus this change so our test cost will be looking

1:07:03 that's all yes and all other operations do not increase potential uh when you add one more element you add one more tree so here delta v here delta p is one uh and when you merge threes you just don't increase the number of trees so here that's all that's all that this is why the amount is first of of the mean is logarithm cool cool that's all that's how you remove me

1:07:55 good basically easy clear by now oh cool that's all that that's how you remove the elements from the financial hits and now finally the final step we need to make this operation decree scheme in constant time unfortunately this is the most hard step in this so i need some room to make this we're close we're very close

1:08:48 what happens when you decrease the key unfortunately many bad things might happen when you decrease the key of the element so if you have some element in your tree somewhere inside the tree so it has some parent it has some children so if you if you decrease the key of this element it eventually may be less than experiment and you need to do something about this you you cannot just sit the element up because it because it will it will be seated up to the root and it costs logarithm time and you want to make it in constant time so you want to do something fast but efficient

1:09:34 unfortunately you cannot do it when binomial trees binomial trees have very fixed structures so every binomial heap of random k always look like this so the structure of binomial binomial 3 is always the same so it's not flexible enough so ah to make decreased key work and past we will introduce another tree so instead of instead of binomial trees we will use another type of tree yeah but basically basically a general tree is not very useful because it is it is always the same you you cannot just remove one remove something you cannot add something it's always the same you just

1:10:21 you're too tight so you need something more flexible uh and let's talk about the tips we'll use different type of tricks uh the trees will look like this so what happens when you have a binomial tree if you have dinner of your friend k let's remember one more time you have k children uh and children have ranks 0 1 2 and so on k minus 1. oh it was called horror quarters sorry about that we have a schedule sorry uh

1:11:07 so what we will what we will change uh we will change this right so now again all trees will have reds so if you have three or crank k so instead of using these trees we'll use different trees if you if you have three or friend k it will have k children as before but what will be the ranks of these children uh it's a little bit different so the first child must have rank at least zero that's quite obvious all over inside zero what the next child should have rank at least

1:11:54 one next child from at least two and so on the last child have ranked at least k minus one so now we have all ranks not equal to this but at least this that's the first change uh what's your main button well let's talk i i remember this i'll

1:12:39 report later i'll explain this method and then we will move to your method okay sorry just not so much time left sorry um so um again we move from these three to these three this is this is much more flexible tree yeah here you you don't you don't you don't don't have to prove exactly these trees in these positions you can move some some some some bigger tree in this position so and the next improvement is that we will allow the tree to lose at most one child so we'll have three of

1:13:25 run k like this and we'll have three of rank plus a k s without tricks like this and this is the tree okay which lost one of its children so instead of having k children it has k minus one children and these children have ranks at least zero at least one and so on at least k minus two

1:14:12 yes two children might have the same right yes ranks of the children maybe this we will draw the the nice thing here um interesting question interesting question imagine you have two trees one tree is e is the three of and two and another tree is uh frank three with one

1:14:59 child removed what is the difference between these trees so in this stream you have two children left child can drink at least zero this at least one and if you have three or four three with asterisks then you have the same it means you had three children and then you lose one of them yeah so again you have two children left child have rank at least zero it's not at least one so what's the difference why do i make this two types of trees like

1:15:47 this trees and these trees what is there any difference between these countries when you use them in your in the big tree it turns out this difference what is the difference imagine you have three of rank four so the three of rank four help four children let's look on the rightmost child please write most child must have rank at least for at least three

1:16:36 so these three heavier and three so we can put this three in this position but these three covering two it is the same as this but the rank is two yeah so we cannot put these three in this position that's the difference so uh why do why why do we care about this book because it will help us to make the martes cost equal to e equal to cos we will maintain these marks and it will help us to make the amortized host here equal to constant

1:17:23 now we remove the entire surprise in terms of forget yes yes yes these three is lost one child with their whole subtriggers so one one sub three of these three is absolutely yeah so for example let's let's move here so so here you may have three of rank 3 bar here and you have counted here here we have zero here you may have one letter six it is the same as zero uh here you might have something like two so you have two children here and two children here and here you might have like one why not

1:18:11 so left most child must have rank at least zero but one is at least zero so we may have two two children offering one why not we may have also make up one one here and one that aspects here so we have rank two here actually that's the perfectly normal fibonacci fibonacci it looks kind of more funny than standard binomial trees so standard fifths are very boring these trees looks cool so what we call here zero here we have one

1:19:00 so this is the correct image keep financial stream we will use trees like this isn't it cool the only property we need from these trees is that the rank of ranks in this tree must be atmospheric difference no when we when we

1:19:48 have a three or five k and remove one child we get the three of front k but with one child removed so this mark shows that we removed one child from these three we can remove at most one child from each tree so we have this triocon k is just a normal trio friend k so it has k children uh with these ranks and these three is three front cape with one shell removed so it's different it's it looks the same again these two trees looks exactly the same but these ramps are different and we maintain this ranks and it will help us to make this time complexity constant

1:20:33 good enough so when you remove one child from from the three of rank three you get three or five three aspects it's not the same as three french two because you can't put three of rank two here but you can put three or five three here why not we might have just before why not here we have node of rank one the node of rank one must have one child

1:21:19 and the this rank should be at least zero two is at least zero so it's it's okay to put three approach two beneath the the node of rank one that's fine i'm not sure if we ever will get some no we may we may end up in situations like this that's perfectly normal yeah so we can put the tree of the bigger rank uh to the parent of this wall right that's fine no no no ramp is rent is not no no no here rank is not the yes yes in the previous lecture we do it we have ranks equal to the length to the deepest leaf it's not it's

1:22:05 not the same here here ranks are just different numbers assigned to each nodes it's it's not connected to the depth of the tree not like before they all called ranks in different data structures but they have different meanings usually so these ranks are different so here the rent is basically the number of children or minus one sometimes cool so we just assigned some numbers to two to these nodes and maintain this property oh finally let's go back i will not prove this

1:22:56 leave the two as an exercise so if you have three like this uh the rank of the root will be no more than c multiplied by logan or some constant you just prove this it's not hard you just check what is the minimal number of elements in the tree okay and then make logarithm and so on so it's so hard leave it for you ah let's go here how to how to decrease the game how to secure the keyboard

1:23:54 uh just believing just by definition this mark shows that we removed one element from this subject we allowed to remove at most one child of any node so so any node of friend k has k children or k minus one children if it has came and came in minus one children it means we removed one child and we have this mark so this mark shows that we removed one child but one child just just by definition we we allow this and even if even when we are allowed to remove one child uh the total the rents will be up to logarithm that's that's the interesting part so even when we allow to remove one

1:24:40 child from each node the ranks will be up to logarithm it will it will not be the same as before so here will be some something different some a little bit bigger but small enough somewhere finally let's go so how to decrease the key of the element so you have the element x and you want to decrease its key it has some subtree here and so on so what do you do what do you do

1:25:26 you take this string decrease the key and then this condition may be broken so if this condition breaks you just take your tree and move it to the root just you just remove x from its parent here you have the list of your so this this all happens inside some of the trees here you have some other trees

1:26:13 this is your hip so inside one of the trees of your fibonacci hips you try to decrease the key of this element so you decrease the key of this element this condition broke so so you take this subtree uh detect it from from its parent and move it as a separate tree to your root that's all now when you removed the child from this element you need to put the mark here so you put them up here that you remove the element from this node but uh it may happen that

1:27:00 you already removed one one child from this note so it may happen that when you remove the x from this parent you already have this mark here it means that you removed two children from this node yeah so this mark shows that you remove one element from the fro from the from from this node and now you remove the second element from this node that's not good we don't we don't allow to remove two children from from the same node so when this happens these three is kind of invalid so it was trioping k with two leaves removed two children removed so what we do we just take this tree

1:27:52 and detach it from a sparrow remove this and move this a to the root list as well we put this and so on and now we go up to three until we reach some vertex which has no mark so yeah we have the vertex x uh decrease the key detach it from parent move it here then go to the parent if the parent have this mark it means we remove two children from this leave so we detach it from the parent and pick here and we do it until we reach some point

1:28:40 so we have come up here detach this move b here and in the end we'll go to some vertex which have no no mark it means what we didn't remove anything from this vertex by now so we put them up here so we put the mark here and that's all that's all that's how you decrease the key of the element you take take the element

1:29:28 uh uh remove it from from from from its parent children list move it to the as a separate tree to the rootless go to the parent if the parent has mark then we detach it from its parent move it here also and so on that's all that's all now when you move the element to the root list you can remove this mark from this list because you only need these marks uh when you when you uh attach this element to some another element just to

1:30:13 satisfy this condition yeah and if the element is the root of the tree you don't need this so for example if this 3a had run k so it was k this okay this was so if it had run k with this one it means that now it has a k minus one children uh then we remove one more chant it means now it has k minus two children so when we move it to this uh root list we just remove this mark and say that it is a normal tree of rank k minus two

1:31:03 that's all so we move all these vertices to the root list and remove these marks go now finally let's calculate the time complexity what is the time complexity what we did we walked uh let's say we have here so imagine we have okay parents uh with marks so we start from here go here here here detach everything move it here what is the time complexity again again again amortized time is time

1:31:49 plus delta v so what is the time here time is simply something like k plus one so remove from here we make like k plus one operations just to go here and to detach everything and put it here so we need to change our potential function in such a way uh that when this happens this potential should be decreased by something like k it's quite easy so what we need to do uh what what is decreasing what we make this person

1:32:35 decreasing is the number of uh number of nodes which have this marks so let's say that potential is the number he we may have a single uh chain of nodes so k may be up to n it's normal the good thing that if k is big the potential function must be decreased by by m if if potential function will be decreased at the same time then the amortized time will be good yes time complexity this real-time

1:33:22 complexity will be in but the amount of complexity will be will be constant in just a second so again how to make a good potential function we need to look on the long long operation and see what what is decreasing when we make a long operation in this case uh the number of nodes which have these marks is decreasing because we move these nodes to the root list and remove this maps let's say so we have before to to get these complexes here we need to have a potential equal to the number of trees num pair of trees

1:34:13 now it's something we all also when we move these elements to the root list we increase the number of trees and we need this number of trees to make this time complexity good so uh let's do let's do the following let's say that the time complexity or let us say the potential is number of trees plus two multiplied by the number of marked nose

1:34:58 eh yes yes the idea that we need to maintain the same potential function for all operations near the destruction let's let's go to group you need to have some potential function which is good enough to maintain all the opera all the uh the amortized cost of all your operations yeah so we need to have so we i need to have this number of trees in order to have this time complexity good yeah so i just add to this number of trees two multiplied by the number of marked nodes then what happens to change of potential here so how potential is changed ah i remove this marks so it is decreased

1:35:47 by two multiplied by k now i move these nodes to here so i have k plus one new nodes here so it's plus k plus one different lines so so so i removed uh marked from here i moved these nodes here so plus k plus one and also i add one more mark here so it's plus two so the total change of potential is my skimmers cables three minus k

1:36:36 that's all now we just add this on this and see here that's all that's how you decrease the key in the match okay again the id is pretty trivial so we just allow each node to lose one of the children and now we when we change something we just detach this with element from each parent and move it to the root each time we do this we remove this one mark and move this element to here so we

1:37:21 here we have plus one potential here we have minus two potential so each operation is decreasing the potential so so you move to the root and each each operation is uh have delta p minus one and d over source for this these all operations are free you you may think about this in the accounting method so you can you can say that each uh mark have a coin of value two and each root have point of value one so like you have two points here and one frame here so each time you go to this you have two coins you spend one coin to move element here and put one coin here so each time you have and here you go to here and put two coins here for future so each time you have

1:38:07 uh this bad element which lost one one of those children you just uh resort to coins for future and in the future when you when you go to this element when you fix this yours you get these two points and to fix something stuff like that okay i hope it's clear enough okay it was the hardest topic of this semester i think but hope it was clear enough so again thank you for joining me let's answer your questions [Music]

1:39:10 do [Music] do [Music]

1:40:06 do [Music] you