Description

What are heaps? How are they related to binary trees? We use losers, winners, and some cards to help us get to the bottom of heaps!

Show Notes

This episode of the Basecs podcast is based on Vaidehi's blog post, Learning to Love Heaps from her basecs blog series.

Transcript

[00:00:00] SY: If you haven’t yet gotten your tickets for Codeland, you totally should. It’s our annual conference about all the wonderful things you can do with code. And besides great food, great talks, and great people, this year we’re offering complimentary on-site childcare. So bring your babies with you and see you there. For tickets, go to codelandconf.com.

[00:00:23] (Music) Welcome to the Base.cs Podcast where we explore the basics of computer science concepts. I’m your host Saron, Founder of CodeNewbie.

[00:00:30] VJ: And I’m Vaidehi Joshi, Author and Developer.

[00:00:33] SY: And she is the brilliant mind behind the Base.cs Blog Series. Today we’re talking about…

[00:00:37] VJ: Heaps.

[00:00:39] SY: This season of the Base.cs Podcast is brought to you by Linode. If you’ve got a personal project, a small business or a big business with lots of data, Linode offers you a secure hosting for all your infrastructure needs. They are a Linux Cloud Hosting provider where you can get a new server up and running in under a minute. Plans start at one gigabytes of RAM for just five bucks a month. And with the promo code CodeNewbie2019, you can get a $20 credit. So go to linode.com/codenewbie and give it a try. Also, they’re hiring. Check out their jobs at linode.com/careers. Link is in your show notes.

[00:01:14] It’s also brought to you by Square. If you’re designing a website or building a mobile app, you’re probably going to want to take payments at some point. Square APIs allow you to easily implement their payment form on your website. And with their In-App Payments SDK, you can add it to your mobile app too. You don’t have to worry about dealing with PCI compliance because they’ll take care of that for you. Don’t let anything come between you and your money. Start building with Square over at squareup.com/go/codenewbie.

[00:01:48] SY: Okay. So today we’re doing heaps. What are heaps? What is this thing that we’re talking about?

[00:01:52] VJ: Well, heaps are a data structure and we’ve been focusing a lot on like algorithms. So we’re going to kind of switch gears back to data structures again, but it’s a little bit more complex data structure, which is why we sort of waited to introduce it. And it’s helpful to know about all the other data structures that we have covered in this podcast so far because heaps are building on that.

[00:02:19] SY: So by data structures that we’ve covered anyway, we’re talking about things like arrays, linked lists, trees that sort of thing, right?

[00:02:26] VJ: Yes. Exactly.

[00:02:27] SY: Okay.

[00:02:27] VJ: And actually we’ve covered a lot of different things and they’re all going to be helpful to us in some way or shape or form when it comes to heaps because they all sort of come together. So in order to understand heaps, you need to have a good understanding of queues, of trees, as you mentioned.

[00:02:43] SY: Okay.

[00:02:44] VJ: A binary research and big O notation and so we’ve covered all those things so far.

[00:02:48] SY: Yeah. We’re pretty smart. Look at us covering things.

[00:02:50] VJ: I know. So many concepts.

[00:02:53] SY: Yeah.

[00:02:54] VJ: And yeah, so all of those are going to kind of help us understand heaps and what to do with them. But I suppose we should probably talk about what a heap is.

[00:03:02] SY: Okay. Yes. Let’s do that.

[00:03:04] VJ: A heap is basically a binary tree with two special properties that it has to follow, two rules sort of.

[00:03:12] SY: Okay.

[00:03:12] VJ: And the two rules are first that it has to have all of its nodes arranged in a specific order.

[00:03:19] SY: Okay.

[00:03:20] VJ: And the second rule is that its shape has to be complete.

[00:03:24] SY: Interesting. Okay. So there’s an order component and a shape component. But before we get into those though, can you remind me what a binary tree is?

[00:03:31] VJ: So a binary tree is a tree data structure where every node, including the root node, can only have two children and the terms that we use to refer to those two children are the left child and the right child.

[00:03:45] SY: Okay.

[00:03:46] VJ: And that’s a binary tree and that’s different from its counterpart where we can kind of say like its cousin, which is the binary search tree. And a binary search tree is a type of binary tree, but there’s some additional rules and that additional rule is that the left child has to be smaller than the parent and the right child has to be larger. So when we’re talking about the value of the left child and the right child, the value matters. You can’t just put any child anywhere. The left child has to be smaller, the right child has to be larger.

[00:04:19] SY: Children have to be in their place. That’s right.

[00:04:22] VJ: That’s not the case with binary trees, a binary tree just has…

[00:04:26] SY: It’s a little bit looser.

[00:04:26] VJ: Yes, it’s a little bit looser and it’s not as restrictive.

[00:04:29] SY: Okay. So binary tree starts with a root and then it has only two children, a left child and a right child, and then a type of binary tree is a binary search tree, which has a specific rule of left child is smaller, right child is larger. So how does a heap relate to either of those?

[00:04:47] VJ: So a heap is basically also a binary tree which just from the definition of binary tree we can visualize that means a heap can only have nodes with two children. We’re never going to be a heap with 15 children. That’s not going to happen. Only are going to be two children per node, but I did mention that it’s not just a binary tree, it’s a binary tree with additional rules that it has to follow. So those two additional properties, the two properties of a heap that you mentioned are shape and order.

[00:05:19] SY: Yes.

[00:05:20] VJ: So when we’re talking about the shape of a heap, we’re talking about what it kind of looks like when you look at the data structure visually.

[00:05:29] SY: Okay.

[00:05:29] VJ: So we’ve mentioned shape a little bit previously. So at some point when we are covering trees, we talked about balanced and unbalanced trees and we got into the shape a little bit there because we were saying that if a tree had 13 right children and 1 left child, the shape of it is kind of unbalanced, right?

[00:05:49] SY: That’s off. Yeah.

[00:05:50] VJ: One subtree is like very long and the other subtree is like maybe non-existent. So that’s what shape is talking about. It’s like, “What does it look like if you sketch it out?” Ignoring the value, it’s just like, “What does it look like?” So the same applies for a heap and when we’re thinking about the shape of a heap and what rules it has to adhere to, a heap has to be a complete binary tree.

[00:06:16] SY: Okay. What does that mean?

[00:06:19] VJ: Good question. When we say that something is complete, what we mean by that is that all of the levels of the tree have been completely filled.

[00:06:31] SY: Okay.

[00:06:31] VJ: So when we talk about levels, like we’re talking about the generations of a tree. So when we are learning about trees, we said like, “Hey, there’s like maybe this great-grandparent node, then it has some children, then it has some grandchildren, then it had some great grandchildren,” and it’s like each level is sort of a generation. So when we say that something is complete, it means that an entire level is filled up with nodes before the next level has any nodes added to it.

[00:06:59] SY: Okay. So if we’re starting at the root and there’s only like one number, right? It’s the root number and then there’s a place for the left child and then there’s a place for the right child, you’re saying I need to have both a left child and a right child filled out before I can have some grandbabies.

[00:07:17] VJ: Exactly.

[00:07:18] SY: Oh, okay.

[00:07:19] VJ: Yeah, and honestly when we’re talking about a complete heap, like that doesn’t mean that you need to have a whole row of grandchildren. The more important part is that you have to have all the children in existence before you add any grandchildren.

[00:07:36] SY: Okay. Okay.

[00:07:36] VJ: You could have a heap where there’s only one grandchild.

[00:07:40] SY: But you can’t have a great-grandchild though.

[00:07:41] VJ: Yeah, you can’t have any great grandchildren then.

[00:07:44] SY: Until all the grandchildren have been born.

[00:07:50] VJ: Exactly. I guess generations have to happen in order is what I’m saying.

[00:07:53] SY: Yes. Okay. Yes. You can’t skip a generation.

[00:07:55] VJ: Yeah, none of that. Then you’re like time traveling or something.

[00:08:00] SY: Yeah. We’ll do that in Heapland. Yeah.

[00:08:00] VJ: I don’t know what would happen, but basically the important thing to remember is the last level doesn’t need to be filled up but the leftmost side of it has to be filled, always. So that’s the other thing with completeness is you’re going from left to right. So if you’re adding a grandchild, you can’t add a right grandchild, you must have a left grandchild first.

[00:08:24] SY: Oh, man, these heaps are very particular. Interesting. Okay. So we talked about shape.

[00:08:30] VJ: Yeah.

[00:08:30] SY: But you said there’s another thing. There’s order.

[00:08:32] VJ: Yes, order. So if you thought that rule finicky, there’s another rule for you.

[00:08:39] SY: Okay.

[00:08:39] VJ: Which is having to do with the heaps root node and order kind of is all centered around what that root node’s value is. So there’s a term called the “Heap Order Property” and that basically refers to how that root node compares to everything else. So there are two options when it comes to order. Either the root node must be greater than or equal to its children and value or it has to be less than or equal to its children and value.

[00:09:17] SY: It can’t be like a middle number.

[00:09:18] VJ: Exactly. It can’t be the middle number. It has to be either the largest number of all of them or the smallest number of all of them in value.

[00:09:25] SY: It’s like if I can’t win them all that I’m going to lose them all. That’s what it said.

[00:09:30] VJ: Sure. I don’t know what that means.

[00:09:32] SY: It just felt right when I said it. You know? It felt appropriate. Okay. I’ll do one better. It’s like when you’re playing a game and it’s like I’m either going to win by a ton or like I’m not even going to play. Do you know what I mean? Like it’s like I quit. It’s like I quit or I need to be the best.

[00:09:49] VJ: Yeah. You know in card games where there are some people who feel really confident that they’re going to lose, so they’re like, “I’m going to bet that I’m going to lose.”

[00:09:57] SY: Yes.

[00:09:57] VJ: It’s like that.

[00:09:58] SY: Sure. Yeah. I’m okay with this because I’m not familiar with this example, but I’m okay with that. Let’s go with that.

[00:10:03] VJ: Because you’re not used to losing. You always win.

[00:10:06] SY: I’m just such a winner that I can’t even relate.

[00:10:08] VJ: You’re like, “What do you mean lose?”

[00:10:12] SY: What is this word? So my root can either be the biggest number of the bunch, of all the nodes or it can be the smallest number of all the nodes. So it’s interesting because when we’re talking about shape, we didn’t really care what the value was on a per node level. We just cared about how it looked visually, but now we’re digging into what the nodes are actually made of.

[00:10:35] VJ: Yeah. Yeah. And actually so I do want to clarify one thing. I realized I said the root node, but actually it’s not just the root note. It’s the parent nodes and I just always think of the root node as the first parent. But if you have a heap with more than one parent node, so if you have grandchildren basically, that means you have children that are also parents. Those parent nodes also need to follow that Heap Order Property. They also know need to adhere to that rule. So that basically means if you have a left child, then the left child has to either be greater in value than its children or less than in value than its children.

[00:11:14] SY: Okay. Can we walk through an example? Because I feel like I get it, but I think I need to see it.

[00:11:19] VJ: Yeah, sure.

[00:11:20] SY: Or hear it, I guess. Okay. So if we do the loser heap, right? We do the heap that is like, “Screw this, I quit. I’m just going to go. I’m just going to lose.” Because I can’t win, I’m going to lose. So I have the smallest number as my root. Let’s give it a number 10, nice and easy, and then now because this is the smallest number, my left child and my right child both have to be bigger than 10.

[00:11:43] VJ: Yep.

[00:11:44] SY: So let’s say my left child is 20 and my right child is 30.

[00:11:49] VJ: Okay.

[00:11:49] SY: So at this point, all my levels are filled, right? So like this is like a complete heap at this point.

[00:11:55] VJ: That’s true. Yes. This is a great example. You do have to complete it.

[00:12:02] SY: So then my left child, my number 20 says, “Okay, it’s time for me to make some babies.” Because that’s what 20s do. And so 20 says, “Okay, I have two spots, I have my left child, my right child,” and now those two numbers also need to be bigger than the number 20 because 20 is my parent-child. No, because 20 is my parent node.

[00:12:25] VJ: It’s your parent node, which also happens to be a child of the root node.

[00:12:28] SY: Yes. Oh my God. When you’re a parent and a child at the same time, Jesus. So then my left child, let’s make that number 40, and then my right child, let’s make that number 50.

[00:12:37] VJ: Sure. Sounds good.

[00:12:39] SY: And yeah, I think that works, right? Did I follow the rules?

[00:12:44] VJ: Yeah, you did. So you followed the shape property because you completed the whole level before you add it to the next level. You gave. 10 two children before you gave 20 its left child, any children of its own, and you also filled up the children nodes from left to right. First you gave him 20 a left child of 40 and you gave 20 a right child of 50. So you followed that order.

[00:13:08] SY: Okay.

[00:13:09] VJ: You followed the shape rule rather.

[00:13:11] SY: Yes.

[00:13:11] VJ: And then when it comes to the order, which is really what we’re talking about when we talk about the values, every single parent node in your heap is less than or equal to the value of its children. So in this case, we have two parents. We have 10, which is the root node, and it is less than or equal to the value of its children nodes. Its two children nodes are 20 and 30. And if we look at the other parent in this situation, which happens to also be a child, it’s the node 20, which is the left child of our root. It is a parent node, but it is also less than or equal to the value of its children nodes, 40 and 50. And bonus, there’s a name for this. I know you called it “The Loser Heap” but I just want to also give it another name. This is called “A Min-Heap”.

[00:14:02] SY: Oh, that’s much friendlier.

[00:14:04] VJ: Yeah. And the reason for that is because the minimum value in this whole group of numbers, in all the nodes is always the root node. So because we know the root node has to be less than its children, then all of its children are going to be greater, and all of the parent nodes follow the Heap Order Property. And in the case of a min-heap, a min-heap’s Heap Order Property basically just says, “The parents, note, always has to be smaller than its children.” So it doesn’t matter if we talk about the root node, it doesn’t matter if we’re talking about any other node in the tree. It has to be smaller than its children.

[00:14:39] SY: Okay. So let’s do I want to say like the opposite of that where the root node is the biggest of everyone. So if we start with the biggest number, let’s say 50, then according to the rules, I have to fill my left child first so let’s give that a number that is smaller than 50. So let’s give that a number 30 and then now I need to fill my right child if I want to continue. So let’s give that number 40.

[00:15:05] VJ: Okay.

[00:15:06] SY: Right? So I have 50 as my parent and then my two children, number 30 and number 40. Since those levels are now all full, I can make some grandchildren. So I’m going to take my left child, 30, and I’m going to give it a child which needs to be smaller than 30. So let’s give it number 10. And then I want to give it another child, which is going to be 20 because 20 is also smaller than 30.

[00:15:29] VJ: Sounds good.

[00:15:30] SY: Okay. That’s not too bad. Yeah.

[00:15:32] VJ: Yeah. And you’ve created kind of the opposite of the opposite structure sort of, of what we just saw. So before we saw a min-heap where every single parent node was going to be smaller in value than its children, in this situation we have two parent nodes, but they’re the opposite basically. So we have every single parent node is larger than its children. And this is called a “Max-Heap”.

[00:15:59] SY: Oh, okay. So Min-Max.

[00:16:00] VJ: Yes, exactly.

[00:16:01] SY: Okay.

[00:16:01] VJ: The names kind of makes sense and it’s kind of cool that we did the example first instead of identifying the names for them because now maybe the names become more obvious why that’s the case. And in this situation, we have 50 as the root node. It is greater than the value of all of its children. And 30, while it’s smaller than 50, it is greater than its children, 10 and 20. So it follows the Heap Order Property again where every single parent node, including the root, is greater than or equal to its children notes.

[00:16:35] SY: Okay. So now that we know these things, what do we do with this information? Why are heaps so important?

[00:16:46] VJ: Well, they kind of give us an interesting way of dealing with data because they are similar to binary trees.

[00:16:54] SY: They feel like it, right?

[00:16:55] VJ: Yeah, you get that binary tree vibe.

[00:16:57] SY: Yeah. It’s like an aura of binary search tree, but like not.

[00:17:02] VJ: Yeah, exactly, not quite. And if you look at these two examples of the min-heap and the max-heap, there are a couple like interesting idiosyncrasies of a heap data structure that set it apart from anything we’ve looked at so far. So first of all, you might have heard me like I keep catching myself and I’m like greater than or equal to or less than or equal to. So the reason for that is you could potentially have two nodes that are the same value and you could have a node that has a child that is equivalent to its value, which basically means you can have duplicates, right? So I could have a node that’s 50 and its child could also be 50 and that would be okay for a min-heap or a max heap because as long as it’s either greater than or equal to or less than or equal to it’s okay.

[00:17:53] SY: Is that allowed in a binary search tree?

[00:17:57] VJ: That’s why this is cool. We just got like this extra power.

[00:18:00] SY: We get to do some cool stuff. Yeah. We got a superpower.

[00:18:03] VJ: Yeah. And you can’t do that in a binary search tree because every single number, every single node has a certain position it has to be in, right? Because in a binary search tree, every left value, every left child has to be smaller than its parent, then you can only have so many numbers. I don’t think you could put in an additional value if something already exists there. You would say, “Oh, the number 2 already exists in this tree. There’s not much else to do.” But in this situation, we could say, “Oh, we have a node with the value 2 and in a heap, you can put another one in.” And you can still follow the two rules of the heap, which are the order and the shape property.

[00:18:42] SY: Interesting. Okay. What else? What else can we do with it that makes it interesting and different?

[00:18:47] VJ: Well, the other interesting thing is we are not having to adhere to one of the rules of the binary search tree. That is slightly annoying. I mean, it’s good. I don’t want to say it’s annoying actually because the binary search tree rules they are what allow you to run binary search as an algorithm, but it’s tripped me up before, so that’s why I need to look. I mean, every time I have to make a binary search tree, I’m like, “Wait, is 10 larger than 11? Where did this node go?” So I always get a little confused.

[00:19:20] SY: How do numbers work? Yeah. Yeah.

[00:19:23] VJ: But the cool thing with heaps is that you don’t have to have a left node that is smaller than a right node. So the left child doesn’t have to be smaller than the right child.

[00:19:36] SY: Okay.

[00:19:36] VJ: And we actually saw an example of us breaking that rule with our min-heap because we had the number 50 be the right child of the number 20, but then the number 30 was the right child of the number 10, and if you think about it, that shouldn’t work in a binary search tree because 50 should always be on the right rather than in a subtree somewhere. So basically we didn’t have to follow the rule of the left node has to be smaller in value than the parent.

[00:20:11] SY: We’re such rebels.

[00:20:12] VJ: I know.

[00:20:13] SY: We’re so cool. We’re so badass. They don’t even know.

[00:20:17] VJ: You see, it’s kind of cool that we had all these other data structures that were like very strict because now we’re like, “Ooh, this is different.”

[00:20:25] SY: Yeah. Okay.

[00:20:26] VJ: Although heap is strict its own way actually because the Heap Order Property is pretty important. That’s honestly if there’s nothing else that we remember about heaps after this episode, we should just remember that the Heap Order Property, which is the ordering of parent nodes compared to their children, that’s really the most important bit about heap.

[00:20:45] SY: Okay. Okay. Cool. I dig it. I dig it. So now that we know what heaps are and what’s so fun and interesting about them, what are we actually going to do with them?

[00:20:55] VJ: Well, because this is a data structure, data structures are pretty much only useful if you can add things to them. So next episode, we’ll probably get into growing and shrinking heaps and then there are also different ways to represent heaps that connect to arrays and they connect to queues too. And so you can basically do a lot of things with heaps and represent them in different ways and add data, remove data. It’s very, very fun times.

[00:21:24] SY: Neat. I’m excited for next episode. And that’s the end of today’s show. If you like what you heard, please leave us a review and make sure to check out Vaidehi’s blog post. Link is in your show notes. Also want to give a huge shout out to Linode for sponsoring the show. Linode is giving you a chance to try their powerful servers built for all your infrastructure needs. They’ve got nine data centers worldwide with new data centers opening this year in India and Canada. Getting started with a shiny new server takes less than one minute so you can get up and running in no time and you can get a $20 credit by using the promo code CodeNewbie2019. Just go to linode.com/codenewbie for more info. And want to say thank you to Square. Square has APIs and SDKs to make taking payments easy whether you’re building a mobile app in iOS, Android, Flutter, or React Native. If you want to embed a checkout experience into your website, it’s super easy. Square has processed billions of transactions so you know it’s tried and true. Start building with Square over at squareup.com/go/CodeNewbie. Vaidehi, you want to say goodbye?

[00:22:32] VJ: Bye everyone.

[00:22:33] SY: Thanks for listening. See you next week.