Video 3-2: Tournament Trees

0:01 heaps. Let's look at the first new data structure um which maybe still known uh still maybe is known to some people. That's the tournament heaps. Um tournament trees I guess uh different names mean all mean in in a nutshell. They're an edge oriented version of a binary heap. What do I mean by that? uh you could have some some elements and these are all going to sit at the leaf level. It's probably too little space.

0:37 They are as always not sorted. So also if you build such a tournament tree from scratch, you would just start with all the elements conceptually at the leaf level of some binary tree and then um in pairs we promote the smaller one up into a new node. So five becomes the parent of these two. Three becomes the parent of these two. Two becomes the parent of these two. And then we're we're done with that level. But we keep going uh up in the same way. So here we have a three. Now here we have a lonely child if you like. It's a single child. We still need to create a node for this child on this level as if there was more to come. So we have a note here and it has an empty right child, right? This is in preparation for maybe someone coming in the future. We insist on having this this empty right child here already uh with the slots here that we're currently not using.

1:44 And then we have one last level which is the root of the entire uh tournament tree. Why is this called a tournament tree? Well, it m it models what you do in a in a knockout tournament in in in sports, say some I don't know uh soccer cup or whatever. Um always two teams compete in the final knockout round, right? Not the the group phase. Okay.

2:12 Um so here note that every element um is present in the leaf but may also be copied to various intermediate levels and also um for every node in here. Let's do this differently. Uh every node has two types of children. It has one child that has the same key and it has another child that has a different key. That's always the case, right?

2:49 So in a way you can say this this tournament tree consists of various paths that are copies of elements somehow connected in a specific way.

3:10 all things I said, but let me copy that to the slides a little bit. We promote the minimum up. Um what this means inductively is that at every node the value we store is the minimum across its entire subree. In particular that's true for the root. So the minimum of the entire sequence is always uh at the root. That's what we always wanted for a heap is also a heap ordered tree by this by this virtue. Right? every element is less or equal than the children.

4:04 Okay. How do we do operations on this? Let's insert a new element into our tournament tree. And say we insert something that is smaller than what we currently have. There's only one spot where a new element is allowed to go, namely the next free leaf. So we put this here. Now in this case, it triggers um an expansion of the the path above. So I'm uh adding a new node here which has uh there's only one child so nothing else changes but I have to recmp compute the path to the root because now this two is no longer the minimum and this two is no longer the minimum. So I'm I'm changing potentially all the way up to the root if in this case the one was this new minimum in the tree. If it's not then it stops somewhere in between. Right? So insert just adds a new leaf, I guess repair is maybe a bit too strong. Let's let's just say recomputee because it's all all it's doing.

5:50 It's just refilling the minima. Oh, and by the way, same as binary heaps, tournament trees have this uh heap shape uh where apart from some some weird cases here uh they're completely full binary trees. So you can store them in a similar way as heaps in an array. It's not exactly the case here with these. So um you have to be a bit careful or you can fill it up to the next power of two. But you can also use an implicit data structure.

6:49 And uh recall then again these will be in the last half of the array. And these are always uh if this is at some position the parent is at index divided by two rounded down position. That was what it was for heaps. The same works for tournament trees. This is unchanged. Okay. So we can do insert. Amazing. We can do find the minimum obvious. That's always in the root. Uh there's not even much to do. Let's let's list it as an operation. It is an official operation but nothing interesting.

7:30 And we can like in binary heaps, we can change the value of an element up or down. It doesn't even depend on that. So if I'm given a pointer to an element, in this case it's a pointer to some uh leaf and a new priority P prime, I can update that and all I need to do is recomputee uh the path to the root. Let me do this on a small example.

8:08 So suppose I'm changing this to a value six. Then uh nothing really changes. I'm just recomputing this this and this. And I may have to go up all the way to the root. But here in this case I stop. And note that uh is a bit different from the insert. For insert, the new elements are always the newly inserted element. But here, if I allow an an increase key, I may get arbitrary updates. If you do a decrease key, then you're only going to promote the element further up, and it's always going to be the new element with a new priority that you write. [snorts] And there's two options for that. Uh a lazy version that um re relies on occasionally cleaning up the mess you create.

9:25 just gets rid of an element so that it's no longer retrieved with future delete min queries. Which means along the equal child edge. These are these these uh gray ones.

9:59 which means the child that has the same key as the current node. Uh thereby I find the leaf for that min. Then you can update the priority of that element to plus infinity.

10:25 and thereby it's never going to be re returned as the minimum as long as there's anything in the heap. Okay, that's kind of a a cheat because the element still occupies a leap. I'm not making the physical structure smaller. So I would have to pair this with some operation that say after half of the heap is is consists of these dummy elements I have to rebuild it from scratch something of that sort. If I don't like that at the slight expense of a of doubling the effort I can also do a proper delete. Um, I wanted to point out that here I'm essentially just using a change value operation to do this lazy delete min. Um, the difference here being the the outside API. For change value, I cannot in principle support this if I'm not giving a pointer to the leaf that I'm changing. Whereas for the minimum, I can because I can follow this roottoleaf path. That's the uh key difference there.

11:33 Uh the eager version swaps the root value with the last leaf. Um I guess let's let's say min leaf which I can find in the same way as above.

12:07 I swap it with the rightmost leaf. Let's do that. I still have it copied, I think. So, let's do delete min here. I follow the path down here to the min. Not a very exciting update. Fine. Um, I could fake fake modify the tree a bit. Let's say the seven was actually a one in this alternative universe.

12:37 Then this was a one and this was a one and this was a one. Nothing else should change except that this one looks more like a weird seven. It's a still coming through what it previously was. If I do delete min on this and I want to do the eager version, I follow this path down to the one. I'm going to swap it with eight. So now in this updated tree that doesn't fit the slide.

13:31 I'll now have this one gone and this one be an eight. What I need to do to fix up the tree is uh fix two leaf to root paths. I have to recomputee from here. That's going to be a five. Now that's going to be a three and that's going to be a three. And I also may have to recomputee from here. In this case, actually nothing changes because this two was already smaller. Oh, the root has to be a two. That's right. Too eager. Yeah. Um, recomp compute always means minimum of the two children.

14:26 Okay. So note that the eager version again needs these two times login comparisons. Whereas the lazy version has a chance to get by with just login. And that's why for a heap sort you can in principle use this this lazy version if you have extra space. So you could make a heap sort variant with one * n log base 2 of n comparisons. If you copy everything to a secondary array and use the lazy delete version. If you want in place then this doesn't easily work.

15:03 Okay, I think this is still a relatively easy data structure. Let's briefly analyze all the operations. Um and then I'll tell you why I am repeating you uh why I'm doing this this data structure with you. insert adds the new element and has to follow one roottoleaf path. So even ignoring the constant that's logarithmic change value I'm updating the leaf and have to follow up a roottole leaf path. So again logarithmic complexity delete min no matter which one I do I have to update a roottoleaf path. So all of them are logarithmic.

15:55 All I can do is logarithmic. Same as binary heaps. Duh. So we've not achieved anything. The reason why I wanted to introduce you to tournament heaps um is maybe twofold. The small reason is if you want to implement multi-way merging then tournament heaps turn out to be a good a better compromise in practice than binary heaps. So that's a kind of a niche application where tournament heaps are often used. Um maybe uh one one comment worth writing down.

16:59 In this specific case, you merge say k runs. Then the leaves would correspond to these runs and the current element in the leaf is the smallest element in this in this run remaining. Then filling up the paths gives you the the minimum of all the elements in the root to put into the output. And then you also remember which run this came from. Uh so you in an implementation don't have to follow down this equal equal path. So then you update this leaf to indeed an always larger element. It's always going to be an increase priority. And this larger element you then have to repair the path and then you can move to the next one. This turns out to be the fastest way in general to do multi-way merging. The real reason why I introduced tournament heaps is that they're the basis of quake heaps, the final data structure of this module.

18:05 And what these are, you'll have to wait a bit. um they're still among those the most complicated data structures. So I wanted to delay them um until we've seen some other things. A small comment both for binary heaps and for tournament heaps.

18:38 There's two versions in both cases. You can either insist on the rigid structure, so the flush left shape that we had last time, or you don't. That's pretty much it. So, you can either have the the rigid shape where in particular um deleting an element only really works from one specific location. You can only ever delete this guy. And if that's not the element you wanted to delete, you have to swap and repair. Uh you could also any binary tree shape really. And just insist on the heap order for both.

19:43 So parent is always larger than the children. And basically all the operations still work. You can still find the minimum in the root. Um insert you could still do as you did it before.

20:13 This was only more restricted that we only allow inserting in one specific place. Now we're even not insisting on that as much, but you might as well. Um and for delete men it's kind of easier now because uh in the binary heaps case the minimum is at the root. So you just throw it out and promote the smaller child until there is no uh child anymore to promote until you've plucked the filled the hole and you've reached the leaf level.

21:14 I mean again you can only do the promotion until there's two null pointers and then you stop and that's when you stop. Visually, you can say there's a a bubble, a hole in the in the heap that is moved down by bubbling elements up. [snorts] And in tournament trees, um it's maybe less clear why this would be useful, but at least you can do the proper delete that we've discussed, the eager delete. without doing the swap. You just follow down to the min leaf, get rid of that and recomputee the path.

22:15 And in both cases, you're now down to one times login, one times the height. in case you care. Um is a bit unclear if you keep deleting and inserting you may deteriorate in the shape etc. Again um usually these are not advisable data structures because giving up this this tree shape implies we can no longer use implicit representation in an array, right?

22:55 At least it's no longer quite as clear how to do that because we have essentially gaps in the representation. If you do the simple thing of keeping the level order, you would have to leave gaps or make the the array much bigger. As I'm I'm ignoring this here, all I'm saying is you could allow your heaps to have a different shape. The key operations are still fine. You can still use them as a heap. Usually this is not very convenient. But again, bear with me. That's the basis of quake heaps.

23:49 I think I haven't made up my mind whether I want to capitalize quake heaps or not.