Video 3-3: Lazy Partition Heaps

0:02 In the next section, we'll look again at something you might remember from last time, but under a slightly different light, and this will make things a lot easier. Maybe you uh in hindsight appreciate it more and swapping the two topics around would make sense. But since we discussed priority cues second, it'll have to go this way around. What I'm talking about is lazy search trees. uh I already mentioned this is again the the full-blown theorem with all the queries that uh they support and the appropriate times. I've mentioned in the discussion at the end of the last chapter that you can use lazy search trees as a priority queue. So we're talking about priority cues. Let's do that. I brought this theorem up again to see if uh if people can can tease this out from the statement. What running times should we expect if we use only um the priority queue like operations on lazy search trees.

1:07 So what that means is all the rankbased queries have as rank always one always the minimum is what we request. If we translate that into our X and C representation, we always split so that this is one. The rank is one.

1:30 That means X is a single element. The minimum that we remove. And the other elements here, this C * X has to be N minus one. So for that to work out uh C has to be n minus one.

1:56 So what that means for x log c is that's essentially login. Uh sorry is there a one over c somehow missing? No it's fine. Sorry forgive me.

2:16 So the queries we expect to take login time finding the minimum or deleting it. Uh delete also login time the extra login doesn't change that. So that's fine. Delete min um will take logarithmic time in the priority cues in all of in all of the priority cues in this chapter. How fast can we do insert or decrease key? Well, for insert, we need to figure out what gap we're dealing with. What gaps will I have? Well, the delete min operation generates for a brief moment in time these two gaps, the left of which is a single element that is right after deleted. So, the gap is gone because it's empty. That means we invar invariantly only have a single gap which is always a one-sided gap.

3:11 So this is only one big thing containing all the current elements which means the size of our gap will always be the current number of elements. So if I insert here this first term vanishes to essentially zero and what I'm left with with is log log n forget this second part um over a longer sequence of operations with many deletements this is not going to help us much. [snorts] So we're looking at log login insert and for change key there's this this funny condition that you move closer to the queried side of the gap blah blah blah we have only one gap and only one side is queried uh the left end here. So whenever I move an element closer to the left which means smaller key smaller priority then I'm in this good situation where the bound is uh the running time is bounded by this. Okay, so we can do decrease key and again um same argument as for for insert that's going to take log login log end time. Okay, so in principle all we need to do is just use the existing blackbox lazy search trees and we'll get a priority queue that's not too bad. uh this is not constant time as initially advertised in the table but is much better than login somewhere in between. Now the the only point is lazy search tries as a black box is a rather fat black box and it turns out here um there's some some rather interesting simplifications you can do that become possible if you restrict the operations as in a priority cube. uh the obvious one I've already pointed out we have this single gap only and you can hence forget about this biased search tree on top etc. So a few parts of the general lacy search trees are just not needed.

5:18 Uh but there's a a more subtle change you can make in how to split intervals and um that's going to further simplify the whole structure. So I decided to include this here again um for basically the reason to to convince you that the the simplifications are worthwhile doing and that the resulting data structure is is really fairly clean.

5:45 Uh this means some of the notation is slightly different. the intervals the iigs there's only one gap so these are just called sj s for for set instead of interval I think no no very good reason apart from um being bit more convenient here and remember the outside of an interval was this the number of elements between an interval and the closest queried side this occurred a lot in the potential for lazy search trees. Here we call that s little s or smaller because it's always going to be the elements that are smaller than a given set. Kind of superficially you've been warned if you want to try to match it to the last chapter's notation. Uh other than that you can forget it and just focus on this from from scratch. Uh here's an attempt to to show how this data structure works as a picture. Maybe you can in hindsight make sense of it.

6:51 Uh each of the piles is an interval of course and they're supposed to keep keep growing to the right. You can uh zoom out a bit from lazy search trees and indeed set up a whole template for spec for for different um priority Q implementations that are all based on this idea of of quicksort style partitioning and lazy uh partition heaps. The ones I'll present you are the I think simplest version of that. There's a few others that also work across according to this template and I have have some other properties. Maybe in the next unit we'll come back to one of them.

7:37 So in a way it's uh a template that has a few things left out. I'll point those out. All of them are a bit like quick sort where you lost interest in sorting at some strategically chosen places.

7:54 And so the state of the world looks like this. You imagine this is an array in with the values from left to right increasing. Then there are certain pivot values where you've made sure that everything to the left is smaller than everything to the right. These are given here. They start counting at two so that the sets start counting at one. uh in particular here uh we want that the sets are contained between these two pivots including the left and not including the right endpoint is not super crucial. Uh also in in the general case this is like in lazy search trees a pivot could be an element that has since been deleted. That's fine. It's just some value that separates left and right. Uh we'll have to keep the number of sets bounded. It's also um something you should uh find sounding familiar.

8:50 The sets themselves we can again just represent as linked lists conceptually. This has the additional nice benefit that we can keep referential integrity. What that means is when you insert an element, I can return a pointer to the location where this element is stored and that location will stay the same throughout the lifetime of the data structure. This is effectively what you want for decrease key because you need to give me a point to start updating an element. I don't know if you've ever wondered how to do this in binary heaps. You can, but you also need to think about it if you implement them. But here um not at all a problem because linked lists we can keep the original node intact forever and just bend pointers around. Now the uh pivot values are kept in a sorted array or in a binary search tree so that we can binary search over the pivot values in logarithmic time in their number and the number of pivot values is is L minus one.

10:02 So to make everything efficient we'll keep these numbers this number L of of sets and pivots logarithmic. And how to exactly do that depends on which variant of these partitionbased heaps you're looking at. Um again you'll find that something uh similar to what we've used in lazy search trees is used here with that. Um even without specifying the details we can already fix what the operations will look like because they're kind of determined from the structure. Inserting a new element means finding which set it should go to. So you do a binary search over the pivots to find the pivots that uh pit around the element like this. And then si is the set where it has to go to. So you can append it there as a new element in the linked list. Again the sets are not sorted. These are in arbitrary order. So you can just append it at the end and return the pointer to this new node.

11:07 That's the insert operation. If you want to remove the minimum, you always find the minimum in the smallest set as one. So, um, you find it in there and that's going to cost you essentially time linear in the size of that set because you have to do a linear scan to find the minimum. you will usually want to do more to make an amortized uh cost more efficient than this. But that's the very least what all partitionbased teams have to do. And a decrease key um you can always imagine like a delete followed by a new insertion. So you just find the element via a pointer in its set, remove it from there and then reinsert it from scratch. Sometimes depending on again the invariance you may have to do more.

12:11 Now let's come to the um specific data structure that I want to show you lazy partition heaps which are derived from this special case of lazy search trees. Uh here what we do upon delete min is we find the minimum in this first set. Yes. But we also split once this set around the median of the set. And this is different from lazy search trees. There we did this fiveway split if you remember. And it turns out here a single partition is enough. Um we also have an invariant on the number of of sets which should be very familiar to you. This is uh essentially the same. There was a factor four here but for a one-sided gap is only a factor two. So we want the number of sets strictly bounded like this. This can only be violated if you decrease the number of elements. Um this is never violated in any other operation because no other operation is generating sets. Delete min does both.

13:15 It adds a new set by the splitting and it removes an element. So it's it's doubly at risk. So there we apply uh a merging rule as I called it back then. Um we called it lazy concatenation which is the more appropriate term but um sometimes you only find the better term in hindsight. um you forget a pivot if the total size of two sets is smaller than the number of elements further to the left. So here's the picture for that. You have two sets. What's to the left of both is smaller than their combined size. If that's the case, forget about this splitter. It's useless. That is the very same as our rule M Uh again um same as for lazy search is not an invariant. We only apply this rule at specific points in time where where we explicitly care about it specifically after deletement. Um and it's not otherwise enforced. It may be violated at any at other points in time.

14:30 And forgetting a pivot means concatenating to two sets since these are linked lists that's bending around a constant number of pointers. And you can show um same same analysis as back then. Analyze the worst case size of sets under this rule. And that means every other set you double the number of elements in it. Okay. Uh with that we can analyze the operations and the analysis will be much shorter than for lazy search trees. Pinky promise. Uh the actual costs of the operations. What do we have to do for insert? We have to binary search over the pivots. That's the log log n log l and we have to append to a linked list constant right.

15:40 That's all that insert has to do. Decrease key in lazy lazy partition heaps is exactly as described in the template. You remove the element from the link list where it is currently and then you reinsert that costs constant because it's a doubly linked list and reinsert cost log login. Again, we're only talking about the actual costs so far. Uh here delete min. So these would have been fine as they are. They're worst case as we want them. delete min not because its cost depends on the smallest on this s1 the leftmost set and that could occasionally be very large. Um we have an additional login for um applying this rule here right.

16:36 So, delete min splits the smallest set and applies this rule C. And the cost of applying rule C is linear in the number of sets that we have. You can do this with one iteration over it computing this number of smaller elements doing the merge if you have to and at the very end uh recomputee your your sorted array of pivots. Um you can you can just keep the keep the pivots in a static array.

17:34 So actual costs per delete min are not good. We need to get rid of this S1. How? Well, with amortization, we can show that if we do many calls of delete min interspersed with other calls in an amortized sense, you only spend this login. For that we'd introduce a potential function which is similar to lazy search trees but way simpler. Uh the overall potential is the sum of the potentials of individual sets. And the potential of an individual set is only this excess the excess size that a set may have on top of how many elements are smaller than it than all of its elements. Right? So this is again the difference between the size of SJ and this. But we only count the excess if it's positive.

18:27 And now we can change we can analyze the change in potential for the operations. If I do an insert, well, one of the sets gets one larger because I add a new element. That might drive up this uh 5 J by one, but that's it. So the increase in potential is constant. For a decrease key, the potential change is actually non- negative um is non non-positive. Sorry. Uh because we may move an element further to the left that makes it makes one set larger. Uh but for the other set we make the set smaller. So those cancel out and we only add another element to the protective size of some elements further some sets further to the right. So the overall contribution is at most nothing.

19:23 That leaves us with the lead min here. We need to see something happen because we need to eat these actual costs of size of the smallest set.

19:33 Now uh there's a few step a few steps that you do in this operation and you can analyze what the potential change is. Partitioning the smallest set here into these two new ones s1 and s_ub_2 that eliminates whatever the potential of the large set was and we gain potential for the two new sets. But the uh potential of of this second set the s2 prime is zero because we exactly make sure that they're equal sized. So these two things will just cancel out.

20:10 That's going to be zero. That's going to be the size of that set, but it's half of the original. So the change in potential is minus a half the size of this set S1.

20:31 We also um delete the minimum that removes uh one protection from all the sets. So we gain a plus L in potential and then um we apply this rule C at the end of delete min. We only need to do it once. Again s simplification over lazy search trees if you remember that we had to do it before and after the the actual query. Uh here we we need to do it only at the end. Uh but if ever something is merged a few slides ago whenever we do this this step of forgetting that pivot it meant that both of these sets are so far from the boundary that their potential is zero. And the rule applies exactly when also the resulting set still has potential zero.

21:27 Right? That's precisely the condition that the size of the new set is less than what it has as protective distance. So all of these um potentially merged intervals uh join sets concatenated sets contribute nothing to the potential change. And the total change in potential summing up the three steps is minus half of this size plus L from step two.

21:59 And this is in up to constant factor is eating up the size of this first set that we had to spend in actual cost and L is bounded by login. Okay. And that that's the whole analysis that shows if you add this up the amortized cost of a delete min is login. The amortized cost of the the amortized cost of the other operation stays within big O of the actual costs. They're only a constant or nothing. Um so the overall uh analysis shows what we claimed.

22:47 Um just to recap, there's a few things that got easier. I mentioned them along the way. So I think this uh is is just a a summary that you can keep for the record.

23:01 What can we say about this? Uh I would I would bet that among all those options that can properly keep stable pointers where elements are essentially forbidden to move after they've once been added to the data structure. Uh this is probably among the fastest options you have to maintain a priority queue. Of course, lo login is not constant. So it's in a way strictly worse. But you need to make the input sizes really astronomical to feel the difference between constant and log login. So what I mean by fastest here is a a statement in practice.

23:42 Another downside which is more serious was this last operation of priority cues taking the union of two priority cues, the melt operation. And there seems no way to support that in a fast way because this this quicksort style um setup seems seems totally unsuitable for that. One tiny uh comment on on lazy partition heaps is an idea that predates them but you can see it as an alternative way to represent the sets. Um in practice using these linked lists is relatively slow. You need to play some tricks to make that better. Um one option is to not do any uh linked lists but rather have the whole thing in one big array. So it's literally like in quicksort we partition ranges of the array around a pivot and then we leave them there.

24:39 uh that that works fine and um gives relatively reasonable uh running times, but there's a few things that no longer work like I pre compared to what I presented. Uh the good thing is that partitioning is probably much faster than on linked lists as low overhead. However, we cannot do the log log end time operations anymore. I can still do binary search over the pivot values. But then if I found an element has to go into a certain position. So this is a pivot. This is a pivot. Pivot. Pivot.

25:16 Now I know I want to insert my new element into this set. But the set is just a region in an array. And there's no space. I can't insert into an array when it's full. So stupid solution would be copy all the elements to the right one step further to the right. That would be very slow because these sets are not sorted. We can do slightly better. We can assuming that we have room at the end.

25:59 copy this element here, this pivot here, this element here, this pivot here, and now I have a free slot for my Y to insert. That's two elements per set.

26:13 Still much better than copying all of these guys one position to the right. But the number of sets is log n log login log n.

26:35 So I can do it with relatively few few moves but not quite as good as before. And stable pointers are also gone. So you cannot easily have both it seems.