Alright, welcome back to the
channel Today. We have a very interesting question. Your
interviewer asks you to implement a binary. We'll get
into all this but first I want to say if you haven't
subscribed to the channel, Subscribe to the channel and
like this video, my goal is to make this the world's largest
resource for software engineering interview questions
that's kind of ambitious and I know I won't do something as
large as you know, Leet code or geeks for geeks, but I want
this to be as helpful and as central of a resource. As
possible, that's why I give every video a table of
contents. That's why I try to keep things structured. So
that's like a study resource. Today's question is implement a
binary heap. So what is a heap and how do we implement it? How
do we even go about this question? So we're going to get
into all of that. So the key thing that a heap offers us is
it offers us either the largest or the smallest number of a
group of numbers. So we have a group of numbers here in a tree
like. And we notice that we have constant time access or
peak. we can pick the smallest elements and it's five. so this
is a heap. We're going to get into all that like I said
before. But first, I want to say that this is a data
structure. A heap is a data structure. A heap is not a
abstract data type. the most fundamental things we have in
computer science to model the way data is stored and
retrieved and and worked with is. Abstract data types things
like stats things like a queue. So if a heap is a data
structure and it's not an abstract data type. What is it? So let's investigate the abstract data type priority
Queue. Okay. So before we investigate what a heap is we
need to see where does a heap come from what is a heap and
implementation of so a heap is a maximally efficient
implementation of the priority queue abstract data type. What is
an abstract data type again, so an abstract data type is a set
of behaviors that we define a certain data type to have so
that we can even call it that data type. So for a stack, we
know we need to support push and pop for a queue. We know we
need to support enqueue and DeQueue so an abstract data type. roughly
speaking is when we support a core API that characterizes
that data type, we can then call it that data type or an. Implementation of the abstract data type, but the reason it is
abstract is because we can do it. However, we want they keep
it abstract and just say we want these behaviors. We don't
worry about how you're going to do it so what are priority
queues behaviors. So this is roughly how the API goes so we
need to be able to check. If the queue is empty, We need to
be able to insert an item. The item could just be an object. It could be any type of object we could pass in or something
like that where we can insert it with a priority. We can tack
on a priority and the highest priority item gets precedence
for removal and then we are able to pull the highest
priority item. We can pull the item with the highest priority
if I insert items with low priorities and then insert an
item with a huge priority that huge priority item is going to
jump in front of the low priority items. So now we're
starting to see how this is going to shape how we implement
a heap and then, of course we can pick an item so we can just
see the item at the. Of the priority queue, which is going
to be the highest priority item. So now let's look at what
a heap is and let's see the types of heaps we have and how
they implement this abstract data type. Okay. So the key
thing we need to understand about a heap is that when we're
doing a binary heap, it's going to be a complete binary tree. What is complete mean it's very simple. All we do is we fill
the tree starting from here and then we go from left to right. Top to bottom, So I would fill like this. I would fill like
that. So for this, do you see how we have the nine the
eighth, the six we feel like this. We go that that right
there right there right there right there. We go from left to
right top to bottom. So if I were to just erase this too, if
I were just to erase that too, do you see how we're no longer
filling from left to right? Do you see how we skip something
right here. So then this tree is no longer complete. so we
can't do that if this is going to be a binary. Heap We must make
sure that this is a complete binary tree. Okay, so we have
our min heap here in blue and then we have this and then we
have our max Heap so the name of the Heap tells us the item
we will have access to in constant time. If we peak. if
we do a peak operation we in constant time, we'll know that
five is the minimum elements of all of these elements in this
assortment of items. So for this max heap our max, heap
tells. Us that nine is going to be the maximum item in this
collection of items. So whenever I get a problem that
is the largest of something the smallest of something I am
immediately thinking I'm thinking of using a heap. I'm
thinking of using a min or a max heap. Now we're going to do plenty of
min and max heap problems, but I just want you to become
familiar with thinking about these structures for sorting or
finding the I or max. in a certain set of items. The heap
data structure is very useful. For that, but today, our job is
to implement one and before I go into this, I want to say
that the code is in the description. As always it is
very easy to follow the code you can start with the code
start with this. It does not matter what we're going to do
today is we're going to do insertions and removal on a
min heap. So our minimum item is going to be the one at the
top so again code in the description, but we're going to
go straight into a walk through with a heap right now. Okay, So
our job is to build a min heap. In this empty space and we have
these items to insert again, the code is in the description
to see how this actually works and what the implementation
looks like, but we're going to just walk through the concepts
here. What we're going to do is insert the ten. so let's insert
the ten. We have nothing here so we just insert 1010 is at
the top of the heap. Okay. So now we have inserted ten now
what we want to do is we want to insert four. so what we do
when we insert an item into a heap is we. Insert it into the
last position. What is the last position? Remember when we fill
our heap to keep it a complete binary tree. We go from left to
right top to bottom, so we go left to right. We don't have
any more room in row one. so then we go to the next row,
which can have two nodes. We can branch two nodes off of the
ten, so we can put an item here. Can I put an item here? Yes. I can so let's put the new four right there but notice
that. There's something wrong here. This is not a min heap
anymore. We have a four here and ten is greater than it. The
item at the top of the heap is not the smallest item. This is
not a min heap. What we need to do is restore the heap when we
insert an item when we remove an item, we're going to do heap
restoration operations to restore it and notice how we do
it. I want you to just keep in mind how we do it and what time
complexity. it's going to entail. We'll talk about
complexities later, but let's restore the heap so. What we
need to do is we need to take the item We just inserted and
we need to bubble it upwards until we have a heap again. So
what I do is. I say four look at my parents. parents are you
less than me. We see that the parent is not less than four. so what we can do is we can swap these items because four
is going to be ten in terms of being small. so four is going
to get the placement. We're going to swap these nodes. so
let's execute the swapping and see where the nodes stand. okay. So
now four is finished. We've restored the heap property. We
bubbled four up while there were parents, we bubbled four
upwards. So now we haven't restore the min heap property as
we can see so now, our job is to insert fifteen. so let's
insert fifteen into the heap. This is not the final
placement. We need to see. Can we bubble this item up to
restore the in heap property so fifteen let's look at the
Parent four is fifteen. Less than the parents do, I beat the
parents in placement, so we see that fifteen is not less than
four. so we see that fifteen is not going to be his parents. It's going to stay put where it is and we know that our heap is
intact. We know we kept it intact before and we know we
kept it intact. After this insertion, we just did right
now. So that means the heap is intact between all of our
operations. What we can do is we can solidify the placement. Okay so now. We have our min heap intact our min he's doing
our smallest item is four, but what happens when our caller
comes along and says they want to remove an item. So how do we
remove an item from the heap? first off? I have to give my
caller what they want. I'm going to give them for the
caller just got there for. but what item are we going to put
in the place of the item that was just removed from the heap
from the very top to keep this a complete binary tree. What is
the only choice we have. The only choice we have is the last
item in the heap, which is the one that is farthest to the
bottom and farthest to the right. so that's going to be
1515 is going to go up where we just had the item removed. so
let's do that. okay. So this is where our he stands, but you
see a problem again should not be sitting right there. So
remember what I said before on insertion, we need to heap
upwards on removal we need to restore. The heap property
going downwards so the item we just put up here. It broke our
heap so what we need to do is we need to look at both children
and we need to see which of these children do I need to
swap into my position to restore the property and I'm
going to keep doing that on the way down. We have this fifteen. we look at both children. If I do not have a left child, I for
sure do not have a right child. Why is that because if I don't
have a left child, I can't have a right child because this is a
complete binary tree. It's a complete binary tree. What
we're going to do is we're going to compare fifteen
against the smaller of the children because what I want is
fifteen says my children. I want the smallest of you to
take my place If I am smaller than you then you cannot take
my place. but if you do beat me smaller of both of my children,
the smaller item of both of my children. If you beat me, take
my place. so all we have is ten. We don't have two
children. We just have ten to compare. Against so what we're
going to do is we're going to see does ten beat fifteen is
ten less than fifteen. We see that ten does beat fifteen so
we're going to bubble fifteen down by swapping fifteen and
ten. so let's swap fifteen and ten now is this a min heap Are
we done fifteen compare it against both of the children. There's no more children to compare against. We can't
bubble fifteen down any further and fifteen is in the correct
place. We solidify the placement. Okay. So now our
caller comes along and now we have some more. Insertions to
do remember when we went to insert an item, we insert it
into the last position, which is farthest bottom farthest to
the right inserts. a twenty let's insert the twenty so
let's see what we need to do is restore the heap We look at our
parents. parents am I smaller than you twenty am I smaller
than 1020 is not smaller than 1020 will not be as parents
twenty will stay where it is and our he is intact. Okay. So
now we need to insert zero. where do we insert zero? We
insert it into the final position. well, we're going to
go down to the right so no more room here no more room here
going to the right now we need to go to the third row. Now the
farthest left we go is here and yeah, we can insert the zero
there. let's do that. so we've inserted the zero but we don't
know if the zero stays there and we can tell the zero is the
smallest item. It's going to bubble all the way up. but
let's see what happens. let's see how we bubble this thing
up. zero asks it's parent. Am I smaller than you? yes zero is
smaller than fifteen do a swap. Okay now zero asks. It's new
parent ten. My new parents 10 AM I smaller than you and then
zero realizes it's smaller than it's parents so we swap zero
and it's parents so let's swap them. Okay. So do you see how
we just bubbled up the item. We just inserted this is how
insertion works in a heap. We put it into the final position. whatever that may be going bottom and then farthest to the
right and then we. It up against its parents zero is at
the top of the heap and we have restored the heap so we can
solidify the positioning is now okay. So now what we want to do
is insert thirty. So again we're going to insert in the
last position go all the way down. as far as we can. We end
up in this row, go far right The farthest right we can go is
right there. so we insert the thirty there. thirty is going
to ask. It's parents 10 AM I smaller than you We see that
thirty is definitely bigger than ten, so thirty will not
bubble up so what we're going to do is solidify. Placement
and we can't bubble up. We still have a heap and
everything's fine. Okay. So now a caller comes along and they
want to remove the smallest item. They perform the
operation and that's fine and what we need to do is we need
to take the last item in the heap and we need to put it at
the top. The last item is thirty now thirty is at the top
of the heap. so what we need to do is we need to bubble it down
and now we have the ability to compare against children and I
need you to pay attention. This is critical. Looks at both of
its children, ten and twenty we want to put the smaller of the
children in 30s position. Why it's a min heap We want the
smallest items to bubble upwards, so the smaller item is
ten. So does the smaller item beats 3010 is less than 3010
beats thirty. So what we do is we swap the smaller item of the
two children with thirty. so we swap thirty and ten okay. And
now we're still sitting at the thirty. So what we. Need to do
is thirty needs to look at both of its children? the smaller of
my two children. We're missing one child here, but that's fine
fifteen and nothing, which is smaller. fifteen is smaller, so
does fifteen be thirty is fifteen less than thirty. Yes. fifteen does be 3015 needs to be higher in the heap because
it's less and this is a mini. so we swap thirty and fifteen
so I want you to notice something do you see how the
farthest we can swap downwards or upwards is the height Of the tree,
so do you see why the complexity of insertion and
removal from a binary heap is going to be log of and the
thing is we're going to have roughly log and levels. We're
going to do a rhythmic work traversing in the worst case. If we go all the way down and we traverse all of the levels
that is our upper bound. for the time we could spend
inserting an item where we need to bubble up or removing an
item where we need to bubble down like we. Just did as we
can see this is a min heap, so let's solidify our placements
again and that was a removal operation. So what we can do is
we can do another removal operation. So let's remove the
ten. The caller wants to remove the smallest item. Let's do
that and what item goes into tens place the last item in the
heap. It's not really last because this is a binary
structure, but the last item is thirty because this is a
complete tree. so let's put thirty into tens place. So now,
this should be pretty rapidly we compare. The two children,
which is smaller fifteen, does fifteen be thirty. Yes it does
so we swap them. so we swap thirty and fifteen okay. So
we've done two removals. So let's insert a two. so let's
insert a two. so we insert a two. what we do is we ask our
parent parent am I less than you Yes two is less than thirty
do a swap two asks. It's parent again. parent am I less than
you? Yes two is less than fifteen do a swap. Okay. So
there's no more parents to check so two. Is now in it's
right place and do you see how we bubble up the minimum item
after insertion. we still have a menu. So now we're completed
two. So now let's insert four. so let's insert four and you
see how we inserted it into the last position. So now four C's
4 AM I less than my parent fifteen Yes swap and then four
asks. It's parent parent am I less than you is four less than
two No4 is not less than two four stops in its tracks and it
stops. There and we have restored our he so now let's
insert negative one where would we insert negative one? We'll
insert it here because this needs to stay a complete tree. Okay negative one we know is going to bubble to the top. We
can see that, but what negative one will do is ask it's parent,
which is less negative one. So we do a swap so negative one
versus a parent two, which is smaller negative one swap
negative one and two. so the key to this is we want to
restore heap when we insert a. We want to double it up when we
remove an item. we want to double down the last item that
we just placed in the removed place. So this is all it is
this is this is the essence of removing and inserting from
binary insert negative three. Finally, so we insert negative
three the last place we can put it is right there. We insert
negative three negative 3 AM I less than my parent. Yes,
negative. three is less than two do a swap negative, three
and negative one negative three is less than negative one. It's
less than its parent. So do a swap. okay. So now, this is the
final state of our heap after all of these operations and you see
how with a heap we see that going downwards, we slowly get
greater in value or you can see it the other way going bottom
to the top. we see we slowly get lesser in value because
this is a min heap. This is what a heap is about. this is what a
binary heap is about. It is all about keeping these quantities
in a gradually decreasing or increasing order in the
structure and having constant time access to. Smallest item. It's not constant time removal removal is going to entail
logic work because we're going to do a traverse of the height
at worst case for insertion and removal. I'm saying constant
time peaking. If we just look at the item, we instantly will
know what it is. So that's what a heap is all about the
complexities are going to look like this. so the time
complexity for the insertion. as we saw is we'll put an item
in the last position, then at worst, we're going to double it
up. The height of the tree, so that's why it's logarithmic in nature
because we can express the height of the tree as a log of
the number of nodes. If you haven't seen my video on logs,
it's very important to watch that because it's great to have
an intuitive understanding of this removal is going to entail
at worst. We're going to upper bound that with logiarithmic work, log
of n because if we remove an item that negative three and
then we put the last item in its place. what we're going to
have to do is we're going to have to bubble this item down. Two is not the smallest item in this heap. We know it's going
to be negative one. This is going to entail at worst. We
might bubble the two all the way back down so again we might
do logarithmic work and that's how we express it because we can
express the height in a logarithmic fashion and again, I have that
video on algorithms. I think it's very important to watch
because it's something that confused me a lot when I was
learning it. that is all for this video. If you like this
video hit the like button, Subscribe to the channel. My
goal is to. Make this the best channel for software
engineering interviews with clear explanations and very
intuitive understandings of these problems that are often
made to be harder than they really are so that is all for
this video.
