Description

Now that you've got your heap, what do you do with it? Shrink and grow it of course! We talk about how to add and remove values from a heap with the help of a few cats.

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 are continuing our conversation on…

[00:00:39] VJ: Heaps! Heaps! Heaps!

[00:00:40] SY: Heaps! Heaps! 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:17] 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:50] SY: Okay. Let’s do a quick recap of what heaps are. What are they?

[00:01:54] VJ: So heaps are interesting kind of data structure. They kind of look like trees, but they have a few more rules so we can kind of envision them as binary trees that have to follow two properties. The first is that they have to follow a certain shape. They have to be complete. And as we talked about in our last episode, they have to follow some sort of order and this is also called the Heap Order Property. So it could either be a min-heap or a max-heap. And that basically just means that in a min-heap, all the parent nodes, including the root node, are less than or equal to their children nodes, and in a max-heap it’s the opposite. The parent nodes, including the root node, are greater than or equal to the children nodes in value.

[00:02:39] SY: Okay. So with these heaps, what can we do with them?

[00:02:45] VJ: Well, we can do the same things that we can do with other data structures, namely we can add things to them. We can remove things. We can move things around and that’s kind of what data structures are good for. So it’s good that we can do that. But yeah. The main things that we really do with heaps in terms of data is usually growing them or shrinking them, adding something or removing something from the heap data structure.

[00:03:15] SY: Okay. So when I think about removing something or adding something to a heap, that feels pretty straightforward, like just I pile on to the heap. Is it that simple or there are things we need to think about? What do we need to know when we’re doing that?

[00:03:33] VJ: Well, it’s interesting because it is simple, but there are some things you have to keep in mind which make it a little bit less obvious.

[00:03:42] SY: Okay.

[00:03:44] VJ: Well, remember from our previous episode and from the recap I just did that a heap has to follow these two properties, right? We have to always maintain the shape and structure of the heap and we also have to follow the Heap Order Property, whatever that is.

[00:03:59] SY: Right.

[00:03:59] VJ: So when we’re growing or shrinking a heap, if we’re adding something or removing something, we cannot violate those two rules. That’s what makes something that seems very simple become slightly more complex because we can’t just like add things willy-nilly. We have to think a little bit with every step, “Hey, are we violating a rule? Are we breaking those two rules?”

[00:04:21] SY: Yeah. We can’t be violators. That’s no good.

[00:04:24] VJ: No illegal activities on this podcast.

[00:04:26] SY: Okay. So I can’t just pile on wherever. I need to be aware, be cognizant of what I’m doing and specifically where I’m doing it is very particular.

[00:04:39] VJ: Exactly.

[00:04:40] SY: Okay. So let’s talk about growing a heap or as you put it adding stuff to a heap. So if I wanted to add a number to a heap, what are the rules? What do I need to keep in mind?

[00:04:53] VJ: Well, I like to think of it as like… there are two rules, but one of them is easier to think about and reason about first than the other. So I think to start, the first thing we want to think about is the rule of shape and structure because the Heap Order Property has to do with the values of the nodes. And even before we get to that, we just want to think about, “Hey, what does this heap look like visually? Are we going to break the rules?” So we’ll remember that in a complete heap, when it’s following a certain structure, you have to fill in the nodes from left to right, level by level. So if we use that logic when we’re growing a heap, it kind of logically makes sense to insert a node at the bottom-most level like starting from left to right, wherever we find the most empty spot because we know if we do that we’re not going to break any rules, right?

[00:05:51] SY: Okay. So that’s like a safe first step.

[00:05:53] VJ: Yeah. that is really the safest. You know, I’ve been thinking about heaps recently and I think that is the safest spot to be in is the leftmost level at the bottom. You always know if you’re going to do something, you kind of want to start from there because it’s like if you add or remove something, you know the world is not going to catch on fire.

[00:06:14] SY: Okay. So besides the completeness of it though, there’s that other rule that we need to follow, right?

[00:06:20] VJ: Yes. The other rule is kind of bumps it up a little bit, bumps us up a notch in complexity. It’s not just that we want to insert it at the bottom leftmost level, we also need to think about what the value of that node is in comparison to its parent.

[00:06:40] SY: Right. Right.

[00:06:40] VJ: And on a larger level in comparison to the whole tree. So when we insert a node, at first we can just insert it based on the structure. But immediately after that, we could be violating the second property which is the Heap Order Property. So for example, if we are dealing with inserting a node and growing a heap that’s a max heap, then we know that the parent node of wherever we’re inserting something has to be greater than in value.

[00:07:11] SY: Okay. Yes.

[00:07:12] VJ: So if we insert a node into that safe spot that we’re talking about but it’s larger than its parent, automatically we’re like, “Oh, this is not going to work.”

[00:07:19] SY: We’re in trouble.

[00:07:20] VJ: This is violating the Heap Order Property.

[00:07:22] SY: Breaking the rules. Okay. So in that situation, what can we do? This is the part that it’s actually kind of simple. The rules are maybe a little bit complex, but the solution is like not too difficult. We can insert a node and we can check how it compares to its parent kind of comparing it to our larger Heap Order Property. So if it’s a max-heap, when we insert the node, we can say, “Hey, are you going to be violating the rule? Are you larger than your parent?” If it is larger than its parent, well, then we can just swap it. We can just say, “Okay, well, you’re larger. We know that the rule is that the parent has to be larger than the value of its children. So we’ll just make you the parent and we’ll just swap the two nodes.”

[00:08:08] SY: Oh, that’s easy.

[00:08:10] VJ: Yeah.

[00:08:13] SY: I’m confused.

[00:08:13] VJ: We’re not we’re not violating our max-heap condition and all we have to do is probably just rearrange some pointers and then you just have the larger node has become the parent and now the smaller node has become the child and you’re still following the Heap Order Property.

[00:08:30] SY: Okay. Okay. But what if this new node is bigger than not just the parent but like the grandparent or even the great grandparent or even then root or even all the way up to the root? Sure.

[00:08:46] VJ: Yeah.

[00:08:46] SY: What do we do then?

[00:08:48] VJ: We’re just going to keep swapping is the answer.

[00:08:51] SY: Just all the way up?

[00:08:52] VJ: Yes. And actually there’s a term that is used to describe this process. It’s called “Heapify Up”.

[00:08:59] SY: Oh. That sounds pretty cool actually. I kind of like that. “What you do?” “I’m heapifying.”

[00:09:05] VJ: I kind of think of it as like bubbling up the tree or like percolating to the top.

[00:09:11] SY: Oh, percolating.

[00:09:12] VJ: Yeah.

[00:09:14] SY: It makes you want coffee.

[00:09:15] VJ: Yeah. Yeah. I want to say cold brew coffee, but not cold brew. The one that’s hot. You know, that one.

[00:09:20] SY: The one that’s not cold brew. Okay.

[00:09:25] VJ: Well, we’ll just keep doing that same process and we’ll heapify the largest. If the node we’re inserting is the largest, we can just heapify it till it’s at the top. And if it’s not the largest maybe it’s like the child of the root node, you heapify until it satisfies the Heap Order Property rule.

[00:09:42] SY: Okay. If you can heapify up, can you heapify down?

[00:09:47] VJ: Yeah, you can.

[00:09:48] SY: Is that a thing?

[00:09:49] VJ: You can heapify down.

[00:09:51] SY: How does that work?

[00:09:52] VJ: Yeah. That brings us to shrinking a heap and deleting a node. So I do want to mention one thing, which is that usually when you’re dealing with a heap, we’ve talked about this in the previous episode, how the root node is kind of cool because you know if it’s a max-heap it’s going to be the largest number in the heap and if it’s a min-heap, then it’s going to be the smallest number. So usually when you’re dealing with heaps, the thing that you’re probably going to be wanting to delete is the root node because we know it’s either the largest or the smallest and there are reasons for this. I won’t get into them today, but we will talk about it probably next episode.

[00:10:36] SY: Okay.

[00:10:37] VJ: The interesting thing about this is that if you delete the root node, well, the moment you do that, you’ve automatically violated an important rule, which is that now you don’t have a heap, right? I was kind of pausing, waiting for…

[00:10:57] SY: I was like, “What’s wrong?”

[00:11:00] VJ: Well, you took away the root node… Wait. They’re not parents. They’re orphans. They have no parents.

[00:11:09] SY: I’m so sorry. Okay. I had no idea where you’re going with that. I was like, “I don’t know Vaidehi, it looks like structurally it looks fine. But except the head isn’t there, I guess. Yeah, that makes sense.

[00:11:22] VJ: We got a zombie heap decapitated.

[00:11:25] SY: Zombie heap.

[00:11:26] VJ: Cleanup on aisle five, please help. Heap was out of control. So here’s the thing. I want to say that you can just be really like, you know, obvious about and just be like, “Oh, I’ll just delete the node that I want.” Well, if it’s the root node, you can’t. And in fact, you couldn’t even do it if it’s like any single node in the tree because you would disrupt the structure and the shape of the tree, right? If you were deleting a leaf node, even if it doesn’t have any children, let’s say that that whole level has been filled up. If you delete the leaf node from there, well, now the whole level is not complete and now you’ve broken the structural Integrity of the heap. So we can’t just simply delete things willy-nilly.

[00:12:12] SY: Okay.

[00:12:13] VJ: But there is that special safe spot in the heap, right, which is the lowest level, the leftmost available spot. We can look at what’s there. And since we know that it’s safe to remove and add things there, we could swap the root node that we want to remove with the node that is in that safe spot.

[00:12:38] SY: Oh, okay.

[00:12:39] VJ: So if you do this, we are going to break one of the rules. I’m guessing you can probably figure out which one it is.

[00:12:46] SY: Oh God! Oh God! With the order one?

[00:12:50] VJ: Yeah. We break the order one. So now we’ve maintained the structural integrity, but the order one’s broken.

[00:12:56] SY: It’s all messed up. Yeah.

[00:12:58] VJ: But we can do the same exact thing that we did when our order was broken when we added a node.

[00:13:05] SY: Oh! We can swap things.

[00:13:06] VJ: Yeah. And actually this is all a long-winded way of me answering your question earlier about heapify down.

[00:13:14] SY: Okay.

[00:13:15] VJ: You can heapify down the node that you just move to the root. So let’s say like you have a child node and you want to swap it with the root, you can swap it with a root. Now the root is in the safe spot to remove. You can delete the root and then you can just heapify the new root down the tree to its correct spot and you can swap so that you find the correct largest or smallest node and you can move the new root back to the correct place.

[00:13:44] SY: That makes a lot of sense. It’s also, what I’m thinking about this compared to all the sorting algorithms that we went through, this is so much easier because it’s very simple. There’s only really one place we can do stuff with and it’s that most bottom, most left place, and that’s a place we can either add or remove things. And then once we do that, then we just swap until everything is in its right place.

[00:14:09] VJ: Yes, but I do want to point out we’re not sorting like the whole heap. All we’re doing is inserting and removing things. There is a way of sorting this data structure, which we’ll probably get to next season, but…

[00:14:19] SY: Is that one a doozy?

[00:14:21] VJ: It’s a little bit more complicated, but I think it’s fun. But you have to know what heaps are.

[00:14:26] SY: Oh, boy, it’s a major doozy.

[00:14:28] VJ: But if I say something that’s fun, you’re like, “Oh, no!”

[00:14:31] SY: Yeah. Get ready folks. It’s coming.

[00:14:34] VJ: Oh my gosh. Well, I think the interesting thing about, it’s actually an algorithm called “Heapsort” and the interesting thing about heapsort is you cannot learn about it if you don’t know what heaps are.

[00:14:44] SY: That makes sense.

[00:14:45] VJ: So conveniently, we took a break from all our sorting algorithms to talk about this interesting data structure.

[00:14:51] SY: Yeah. So shrinking and growing heaps has been frankly just a lot easier than I expected it to be. I thought it was going to be way more complicated, but it sounds like either way there are some simple rules to follow and our main goal is to make sure we don’t mess with the integrity of the heap.

[00:15:07] VJ: Yeah. Yeah. Those are the two things that you always have to keep in mind. But I think once you start thinking about heaps as like a little bit of a specialized structure, you always look at a heap and you’re like, “Okay, before I do anything, think about these two rules.”

[00:15:20] SY: Don’t mess with it. Yeah.

[00:15:22] VJ: It’s like a little finicky, like a cat. We’re like, “I don’t want to pet it unless its tail is up.”

[00:15:28] SY: Is that how cats work?

[00:15:29] VJ: I don’t know. I was about to ask you. Is that what it’s going to do? I know there’s a certain time where if a cat’s tail is up, you do or don’t want to pet it. One of them means they’re happy and the other one is like, “Hey, go away.” Anyways, heaps are cats or cats are heaps. What if you had a heap of cats? That seems hard.

[00:15:52] SY: And now we have the episode’s title. Wonderful! And not only do we have the title, but this is actually kind of a special episode because we are, what is it, halfway through all of your blog posts?

[00:16:04] VJ: We’re halfway through the series and we’re at the end of the season. So that’s good.

[00:16:08] SY: Yeah. Okay. So we went through half the blog post in like a year and a half, a little less than a year and a half?

[00:16:15] VJ: Uh-hmm.

[00:16:16] SY: That’s not too bad.

[00:16:17] VJ: Yeah. We’ve been busy this past year and a half.

[00:16:19] SY: We’ve been working. We’ve been doing stuff. We’re learning. Talking about cats and their tails and everything, it’s been great. So I’m excited to kick off the second part of your blog series next season.

[00:16:33] VJ: Yeah, can’t wait.

[00:16:35] SY: 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:17:41] VJ: Bye everyone.

[00:17:42] SY: Thanks for listening. See you next week.