Video summary
The video introduces a common coding interview pattern known as "Two Heaps," which is primarily used to efficiently find the median of a data stream or an array without storing all elements in a single sorted list. The core concept involves maintaining two heaps: a Max Heap to store the smaller half of the numbers and a Min Heap to store the larger half. This approach is necessary because sorting every time a new element arrives would be inefficient, and simply storing all values might exceed memory constraints. By splitting the data into these two structures, the algorithm ensures that the median can always be derived from the roots of these heaps, which represent the largest value of the lower half and the smallest value of the upper half respectively.
To understand how this works, it is essential to first grasp the properties of a heap, which must be both a complete binary tree and satisfy specific ordering rules. A complete tree requires that all levels are fully filled from left to right before any new nodes are added to subsequent levels, similar to filling parking spots sequentially. Additionally, a heap must have its root as either the minimum or maximum value of the entire structure; if the root is the smallest value, it is a Min Heap, and if it is the largest, it is a Max Heap. The video illustrates that any deviation from these structural rules, such as leaving gaps in earlier levels or having a root that is neither the min nor max, disqualifies the tree from being a valid heap.
The algorithm maintains balance between the two heaps to ensure accurate median calculation, specifically ensuring that the Max Heap always contains either the same number of elements as the Min Heap or exactly one more element. When a new number is added, it is initially placed in the appropriate heap based on its value relative to the current roots, but then a rebalancing step occurs. If the Max Heap ends up with fewer elements than the Min Heap, the smallest element from the Min Heap (its root) is moved to the Max Heap. This process guarantees that the size difference never exceeds one, allowing the median to be found instantly: if the heaps are equal in size, the median is the average of their two roots, and if the Max Heap has one extra element, the median is simply the root of the Max Heap.
In conclusion, the Two Heaps pattern provides an optimal solution for dynamic median problems by leveraging the properties of Min and Max Heaps to keep data partitioned efficiently. The implementation involves a continuous cycle of pushing new values into the heaps and popping the necessary roots to maintain the size invariant where the Max Heap is never smaller than the Min Heap. This method allows for constant time retrieval of the median after an initial logarithmic insertion cost, making it significantly faster than sorting approaches for streaming data. By strictly adhering to the structural rules of complete trees and heap ordering, developers can solve complex interview questions involving running medians with ease and efficiency.
Read the full video transcript
what's up guys Mike the coder here today
we are going to talk about two heaps
which is another coding interview
pattern I know I've said I was going to
do the two new series today but um I
feel like we should finish this series
first and then we could be on our way
and um yeah let's just let's try to
finish this series first so we're going
to talk about two heaps and the gist of
two heaps is actually not that difficult
it's basically we're going to maintain
two Heat
one is going to be a Max Heap and one is
going to be a Min Heap okay so let's
actually give out an example um let's
say we are trying to find the median of
an array or something a data stream or
an array this is generally what speaking
what happens a lot in uh coding
interviews they give you like an
arbitrary number of elements to add yada
yada
but this is this pattern will you could
use it on most interviews you would have
to use a heat somehow sooner or later
you'll probably have to use a heat you
guys don't remember how medians are so
let's say I give you an array of numbers
like this right an array of numbers 1 2
3 four five the median will be the
middle number it'll be the will be the
middle number here so if I were to cross
a value from the first one and then the
last one and the second one last one
last second last one from the beginning
and cross the back back one the middle
number would be three so this median
would be three okay now now the only
time when the median is not this is if
we have an even length of numbers so
let's say we have 1 2 3 4 5 six right in
this case if I were to repeatedly uh
cross out the beginning and the last
number see the beginning second one last
number we have two values here three and
four so the median in this case is will
be the sum of them divided by two right
it will be the average of them so it
will be 3 + 4 and then we divid by two
which will give us uh 3.5 okay so that
would be the median of this okay so what
is the um easiest way to do this well if
you have
like in um competitive programming the
easiest way would just be to sort them
and then just get the middle value right
because if you sort the values and then
you have the length of the array you
could just get the middle value and if
it's even you could just like like add
the the middle value the middle value of
this one and that one divide by two
right but we can't do that in this
coding interview because uh for some
reason we can't store all the numbers
together and we can't just store every
value we see because that just takes too
much storage so before we get started
some some of you guys don't know what
heaps are so let's actually go over what
a heap is so a heap is a complete tree
one there's two properties one it is a
complete tree two it it has either the
minimum value is on the top of the root
or the maximum value as at the top of
the root so this would be example of a
complete tree so so let's actually go
over what that is so one it is a
complete
tree so it has to be a complete tree too
the the root must be a Min or
Max Okay so
uh what is a complete tree so let's say
I have values like this 1 2
3 4
five 6 7 okay this is a complete tree
why because all the values have been
filled up before the next row and all
the values have been filled up from left
to right okay so what is a let's see
what's not a complete tree
this is not a complete
tree not a complete tree why because
this six should have been on this
side this six should have been
here remember all the values have to be
filled up from left to right and if you
think about it my old CS teacher would
have been like they're like parking lots
okay you have to fill up the values
between the left and right until they're
all completed okay so we cannot have
random values like this this is not a a
complete tree okay all right what is
another thing about a
Heap what is also not a heap okay
um this is also not a heap right because
not a heap because this six should have
be on this side the left side the values
have to be filled up before the next
before the next level right all the
values have to be filled up until the
next level so this six should have been
over here okay they have to be filled up
they're like parking lots all these
notes from left to right this this has
this has to be filled up this has to be
filled up this has to be filled up this
has to be filled up right this six then
this has to be filled up then this then
this
okay they have to be filled up before
the next
one what else is not a heap this is not
a complete tree this this is not a
complete tree why because this four
should be on the right side each level
has to be filled up between before the
next okay
this four has to be in this side they
have to be filled up okay they have to
be filled up okay likewise this is also
not a complete tree we have a four and
then a two here not a complete tree this
four should be on this side okay that
I'm just saying okay and what
else the second property is that the
root has to be in the Min or Max so out
of these values in this in this tree
this is a Min Heap why because this root
is a small smallest value of all these
values one is smaller than two one one
is smaller than three one is smaller
than four okay the root is the smallest
value okay what is the other property it
could also be the largest value so if I
have six and then we have one two 3 four
yes this is a Max Heap why because this
root is the largest value it's the
largest value of this Heap okay largest
value 1 2 3 five six this root is the
largest value that's why we consider it
okay so that's what that's what makes
this a heap okay also it's because it's
a complete tree all the values are
filled
up from left to right they're all filled
up in this tree okay so now that I got
you the gist of the theory behind heaps
how do you do this
problem so remember we need to get
the we need to get the median of values
in this in this array okay so what are
we going to do what we're going to do is
we are going to have
a Max Heap for all the values that are
smaller than um than the middle and uh
that than half of the array and a Min
Heap for all the values that are larger
the largest for the larger half of the
array okay so to do that let's have
let's think about this we're going to
Let's consider adding values here okay
so this one this left side would be Max
Heap and this right side would be Min
Heap so let's start from left to the
right side I'm going to add one to my
Heap okay I'm going to add one to my
Heap so one is going to be in here okay
then I'm going to add two remember this
is a Max Heap so this two becomes here
goes here right it becomes a Max so this
two would actually
be right here it reorganizes itself to
be right here okay I'm going to add
three it's going to reorganize itself so
when I add three it'll be three 1 2
okay bam that's our Max Heap here and
the right side four five6 let's add four
four will be the Min Heap right
four add
five bam add six bam so now that we add
our all our values what what do we do
well since we have the ma
the we have the maximum value on the
smaller end of the sides on this side
the maximum value the smallest end on
the side we have the three so we could
just take the root of three which would
be three and then if we want the
um smallest value smallest value for the
the right side Min Heap the root will be
four right four so we could just add
these Up 3 + 4 / two will give you
3.5 okay so bam that's that's the
fastest way to do this okay that's the
fastest way okay all right so what if
the array of numbers is um odd right if
the array of numbers is odd well the
median would be three right the medium
would be three so in this case our Max
Heap should have one more than
the then the Min Heap so in this case
our Max Heap let's say I had one here
right and then I had two and I had
three like that and then our Min Heap
would have four and then five okay so in
this case we need to return
the the um the middle value and it would
just be the root of the max heat so it
would just be three okay so if we have
an odd number of values and they're odd
right we'll just return the root of the
max Heap okay so in our situation we're
always going to have one more element
for the max Heap the max Heap will
always have one more element okay that's
just I'm just making you sure you guys
understand this Max Heap will always
have one more element so in the case
when it's
odd right um we'll just return
the the first value of the max Heap okay
okay so uh how do we make sure that the
max Heap always has one more element we
use uh we use a way called balancing so
I'll show you guys what that means all
right guys so how do we make sure that
we balance it properly so the simplest
way to do it is every time we add
numbers to both our Max Heap and Min
heap if the value on the left side of
our Max Heap is smaller than the value
on the right side of our Min Heap um
we're just going to remove the top
node of this value and then we'll just
add it to the max Heap so we'll move the
top node and then add one more to the
max Heap that's assuming that the number
of values in the max Heap is smaller
than the Min Heap right so we just
remove that and put it there and then
we'll do that every single time when
reorganizing when we have the max that
is smaller than the number of values in
the Min Heap okay so that's basically
what reorganizing will be so I'll show
you guys the code of
that right
now so um
hope you hopefully you guys can see this
can you guys see
this bam
okay
so this is uh this is what the code
looks like okay this this add number is
a reorganizing okay low will represent
the max Heap and then high will
represent the Min Heap okay
so they just represented this this way
so let's actually go over an example of
how this
works while we're adding the values to
make sure it's getting reorganized
okay so Min Heap and Max he and Min Heap
okay
so okay um we start the value first a
one we push it to low so low gets pushed
here um high will also get pushed with a
value one this is just making sure
that lowest top is one so we're making
sure both of them have the same number
currently and then what we're going to
do is we're going to pop low so low is
going to we're going to remove this it's
going to be gone okay now um since low
is smaller than high so the number of
elements here in the max Heap is smaller
than number of elements on the Min Heap
um we're going to push whatever values
we're going to remove the value on this
route and put it in here so we're going
to take this and we put it in here and
we're going to remove it so what we're
going to do that is uh basically we push
one the root that was on here and then
we remove it so now it's gone okay so
that was one now let's go to two so
right
now currently we just
have currently we just have currently is
um one here right because after all the
removing this is what we have all right
so now we have two uh what are we going
to do so low is going to push two so two
is going to get pushed onto low so it
looks like that and then high is going
to get pushed Low's top so what is the
the top what is our root of our Max Heap
it's two so our Min we're going to add
two here also we're going to pop the low
so then this is going to be gone so this
is going to be
gone two is going to be gone all right
is low smaller
than is uh the size of the max smaller
than the size of the Min Heap nope so
then that's that we do that and we go to
the next value three so let's actually
get rid of that so so now our values
will have one and
two right and then we're done with this
we're go with
three okay um what are we going to do
we're going to
push three onto low so three goes here
okay high is going to push lows top so
hi is going to push lows top lows top is
three so we're going to hi is going to
add three also okay now we're going to
pop low so this is going to be gone
three is going to be gone and we're
going to have that is the max Heap the
size of the max Heap smaller than the
size of the Min Heap yep see number of
elements in Max Heap is one number of
elements in Min Heap is two so we need
to remove the the top note and put it
replace it here so we're going to move
the top no to and then add it to here
okay so now we have one two and then
three here okay so now
let's get rid of this so we have one two
and then we have three here okay so now
um now we go to four what do you four we
push the load push
four oh this is a Max he my bad my
bad and three here uh low push four so
then four gets pushed so we're going to
have four here and one two and there's
going to be three here
okay um high is going to yeah okay High
push lows top lows top is four so n is
going to have four
here low pop so we're going to pop four
out so this goes back to become 2
one okay it's going to reorganize become
one two1 is a number of values here
smaller than number of values here um
nope they're not so we don't do anything
and let's go to
five five low push five so low is going
to have five so we need to reorganize
this it's going to be five one 2 512
okay um high is going to push the top
which will be five so then we're going
to have five added to the righted side
here low do pop so we're going to remove
five so then it's going to rebalance
itself and
become 2 one re balance up become 2 one
okay and then is low smaller is the
number of elements in low smaller than
the number of elements in high yep we
have two elements in low and three
elements in high so what we're going to
do is we're going to we're going to push
the Top Value remove the three and put
it into to the max keep so move the
three and then we're going to put three
into our this one so then in the end we
have here's what we're going to have in
the end um three one two and then four
five on the left side so again we're
going to have
three
Min three one two and then we're going
to have four four and then five
okay and yeah that's all we have to do
okay so then the left s side will have
three elements the right side will have
V have two elements and yeah that's it
now if we want the maximum size um now
if we want the maximum number of
elements right
now that if we want the median right we
just have to check is the number of
elements on the left side greater than
the number of elements on the right side
so if they are that means that the the
size of this
array is odd
right the size of the array is is odd so
then we just have to take the root so we
have to take three and return three okay
and if they're not that means that both
of the sides are even right they both
have the same number of elements so in
that case we just add them up and divide
it by two we just take the root of both
of these add them up and divide by two
okay so yeah that's how this uh two
heaps pattern works I hope you guys
understand this video it is uh this
pattern is not that difficult to
understand make sure you have two heaps
and you could use this to find medians
you could use this to find anything else
and I hope you guys enjoy this video
yeah this I'll show you guys the code
again this is the code the low is the
max Heap uh is a Min Heap and that's a
priority CU there and then um yeah
that's this is how the code works this
whole low. push numb then high. push
lows top which is is just like getting
the values at top and then removing the
values on on the moving the root on the
on the max Heap and just balancing it
and then we have to make sure that the
low has one more value than the
high if it needs it like if it needs to
have one more value than the high right
then we do that all right right now if
you want to find the median we check is
the Min heaps uh is the max Heap size
greater than the Min Heap size and if it
is we just return the root of the max
Heap otherwise we just add them up and
divide it by two so in this case We'll
add them up and divide by two and they
multiply by 0.5 but you just add them up
and divide by two and they cast them
into a double because for them it was an
integer before but they cast it into a
double because it was an integer before
but yeah that's what you all all you
have to do I hope you guys enjoy this
video that's this is just how um the two
heaps coding interview pattern Works
rate com subscribe I'll check you guys
later peace