Everybody what's going on says Caleb with Deb sloes dot com and in this video we're going to be talking
about two very important data structures that you need to know about.
One is called the heap and the other one is called the stack.
Now they're very similar in some ways but they're also very different in other ways.
So we're going to learn the key differences.
What makes them sort of similar what makes them very different and you need to know the distinction
between the two of these is really important.
So let's begin with the heap.
Now you can think of the heap like a giant pile of values.
You can see it here.
There are two kinds of heap.
There is what's called a mini heap and a max heap.
And so we're going to be focusing on a min or minimum heap in this video because the max heap is literally
identical just the opposite.
So what you see in this video for the heap you can just flip the concepts and the same thing applies.
Pretty cool.
So a mini heap is organized from least to greatest from top to bottom.
You can see the smallest values are at the top.
They branch out and they begin getting a little bit larger.
They continue to branch and get larger and larger and larger all the way down.
As you branch down the heap those values increase.
OK.
So each level down has bigger and bigger values.
That's why it's called a heap.
We have the big things on the bottom as foundation and a build up and up and up and up.
Now it's also structured like a heap it's like a big pile of data and a maxi.
Like I said would have the greatest values at the top and the lowest at the bottom.
So basically a heap consists of parents K parent nodes and children on the left and right of that node.
Now every node can have one or two children and each node in and of itself is a parent unless of course
it doesn't have nodes if it doesn't have a left or right child node sort of like like like a family
tree.
But it's kind of actually kind of weird if you really think about it too much so just think of it sort
of like a family tree.
They're all connected.
Now each node in our stack has a particular index.
OK.
And it's going to go from top to bottom from left to right.
And what that means is that we're going to start with zero.
Of course at the top of our heap and then the left child node is going to be one the second the right
child though is going to be two three four or five all the way through the entire heap top to bottom
left to right.
And because of that order we can easily use an array to house a heap which is pretty cool.
Now we can easily access any of the nodes in our heap by just doing a simple calculation on whatever
index the know that we're working with has.
So for instance if we were working with the index for and we wanted to know which node was its parent
we would take the index minus 2 and then we would divide all of that by 2 and that's going to get us
the index of its parent.
Pretty cool.
Now if we are dealing with a parent node like let's say that 4 for instance is a parent node if we want
to get the index of the left child node all we have to do is do index times two plus one to get the
right child node we need to do index times two plus two.
Pretty cool.
That's how we're going to do it.
And that will get you the index of whichever child node you are trying to find as well as the parent
nodes.
Very very cool stuff.
But this heape already has values in it.
What happens if we add a new value.
Well if we're using an array when we add a new value it's going to append it to the very end of our
heap which in this case would be down at the very bottom.
Now of course this value is too small.
It doesn't fit in the heap.
But what we're going to do is basically using a couple of functions you can bounce it up to the top
by comparing it to the nodes around it.
It'll be out of order and in order to fix that we're going to go ahead and basically well see does it
fit.
Is it less than it's parent.
Cause we can get that index right.
If it's not less than its parent then we're going to flip it with its parent and then we'll compare
that node to its parent above if it's less than the parent.
We're going to flip it again until we get to a place where it fits where the one above it is less the
one below it is greater.
And we can access all those indices using our little functions there that we talked about index minus
2.
Divided by 2 and x times 2 plus 1 et cetera et cetera we can access all of it and determine its place.
Very very cool stuff.
That's how a heap works.
In essence like I said a max heap is the opposite.
So let's move on to the stack now.
Another very important data structure and you can think of a stack like well a stack.
OK.
Think of a stack of plates a stack of boxes a stack of laptops a stack of cans of spray cheese don't
actually try that it's pretty messy.
Don't try this at home folks.
But you can think of it as a stack.
That's why it's called a stack and something important that you need to know about a stack is that it
is a leaf no data structure.
L I F O that stands for last in first out.
And what that means is exactly what it sounds like.
The last item you put in is going to be the last item you take out.
Think of a stack of plates if you had a stack of 100 plates you wouldn't try to pull out the 99th plate
on the bottom.
You'd pull off the top because that's easiest need break your way down through the stack.
That's how a stack is going to work.
The last item in is the first item you remove.
Just like a stack of any physical object so a stack has a few different functions that can be performed
to interact with the data.
Push is one of them.
Pop is another one and peek is a third one.
So push push is a function that's going to push a new element onto the top of our stack.
So if we begin with zero items we would call push once to push in the first item if we wanted to stack
another one on top we would call push again and add in that item.
So that's how it works.
Push is going to add an item to our stack.
OK pop the function what it's going to do is it's going to remove the top item from our stack and then
return that to wherever we call the function.
So if we wanted to basically remove an item and then access whatever value it had we would call pop
because it's going to pull it off and it's going to give us the value which would be really helpful
if you know maybe you deleted something in an app but you wanted to give a user the ability to undo
it within 15 seconds it would pop that off and you would still have reference to the data in memory.
And then if they decided not to get rid of it you could just let that expire and get removed from memory.
That's just one potential use.
Furthermore peak is the last function and peak is going to allow you to essentially look at the top
item.
But the cool thing is that peek doesn't actually modify the stack what it's going to do is it's going
to let you see what the value is it returns the value but it's not going to remove it or add it.
It just allows you to look at it in view only mode if you will.
That's what Peke does.
So since a stack is so linear in nature it's perfect to use with arrays in code so you don't need to
build your own fancy data type or or you know way to hold all of the stack data.
You can just use an array because it's a very very linear data type.
So this is in essence how a heap and a stack work.
They're very different but they're similar in a few ways.
I'd be surprised if in a coding interview you weren't asked about a heap and a stack those things together.
I would be surprised if you were not asked about that.
So to recap the heap and the stack are both data structures very common programming data structures
the heap is a hierarchy of values going either from least to greatest.
Each node has children or can have children and each child node has a parent node and the parent node
is always less or greater depending on whether it's a least the greatest heap or a greatest to least
keep the stack is a last in first out data structure.
That means every item we add on is going to be the first item that we take off.
K we can peek to see what's on the top.
We can pop values to remove them and we can push new values on the heap and the stack.
They're both very important data structures so study up make sure you understand these concepts so that
you could create them yourself in code.
It's very very important to know about.
This is Calleigh with Debb slopes dot.com.