Computer Science Engineering (CSE) Exam > Computer Science Engineering (CSE) Videos > Build Max Heap Algorithm and Analysis, Programming and Data Structures, CSE, GATE
Build Max Heap Algorithm and Analysis, Programming and Data Structures, CSE, GATE Video Lecture - Computer Science Engineering (CSE)
FAQs on Build Max Heap Algorithm and Analysis, Programming and Data Structures, CSE, GATE Video Lecture - Computer Science Engineering (CSE)
| 1. What is a Max Heap? |  |
Ans. A Max Heap is a complete binary tree in which the value of each node is greater than or equal to the values of its children. In other words, the parent node has the maximum value among its children. This property is known as the Max Heap property.
| 2. How do we build a Max Heap? | |
Ans. The algorithm to build a Max Heap is as follows:
1. Start with an array representation of the binary tree.
2. Iterate through the array from the last non-leaf node to the first node.
3. For each node, compare it with its children and swap it with the maximum child if necessary.
4. Repeat this process until the entire array is in Max Heap form.
| 3. What is the time complexity of building a Max Heap? | |
Ans. The time complexity of building a Max Heap is O(n), where n is the number of elements in the array. This is because the algorithm iterates through the array once and performs a constant amount of work for each element.
| 4. Can a Max Heap be built in-place? | |
Ans. Yes, a Max Heap can be built in-place. This means that the Max Heap can be constructed directly within the input array, without requiring any additional space. The in-place construction of a Max Heap is achieved by starting from the last non-leaf node and applying the necessary swaps to satisfy the Max Heap property.
| 5. What is the significance of Max Heap in programming and data structures? | |
Ans. Max Heaps have various applications in programming and data structures. Some key uses include:
- Efficiently retrieving the maximum element from a collection of elements.
- Implementing priority queues, where elements with higher priority are given more precedence.
- Sorting algorithms like Heap Sort use Max Heaps to sort elements in ascending order.
- Efficiently finding the kth largest or smallest element in a collection.
Overall, Max Heaps provide a fundamental data structure for solving various problems efficiently.
Text Transcript from Video
given an element array and add a
containing and elements okay so what is
the total total time required or how to
build a max-heap
so I have already shown you that we are
going to use a Mac cp5 function which
I've just shown you so using the max if
a function we can build a heap as I will
show you how to do it with an example we
already seen it anyways right let the
example live like this
okay now you just see what is the
complete variety representation of this
so if I try to write it in a form of
almost binary tree we are going to get
this
I think this market one two three four
one two three four eight elements right
now one thing is how this algorithm is
going to work is initially a dot heap
size equal to a dot length it is assumed
that by the end of this procedure we are
going to make a dot heap size equal to a
dot length therefore it is setting now
if there are eight elements it is saying
that heap size is going to be eight so
why do we need that eight is inside this
heap we are always going to check Mac
simplify we are always going to check
whether element is having a left child
or not let us say we have read this
index then this is having left child but
it is not having right child just to
know that this right child is not there
we should set the heap size to be 8
otherwise what happens is it will try to
refer to 9 again and now for loop this
for loop is running from a dot length by
2 down to 1 the reason is this if I have
8 elements I have already shown you that
the leaves will run from 8 by 2 plus 1
to 8 so what is 8 by 2 plus 1 5 to 8
right so the leaves are 1 2 3 4 starts
from 5 5 6 7 8
therefore leaves are going to run from 5
6 7 8 right so that is what is the
meaning of this and what about the non
leaves 1 2
n by 2 1 to N by 2 or the non leaves and
then n by 2 plus 1 to N or the news
isn't it so these are the non leaves and
these are the leaves right so we have to
go to every non leaf one by one but then
we have to start from the largest index
that is why it is going to start from
largest index and we are going to apply
the heapify which means what is the
first largest you know non leaf for
therefore applied heapify here if I
apply heapify here then three will come
here and 0 will go there because you are
doing max-heapify and then we had
applied hipfire at three from four three
two one that is the way right if I apply
maxify here then it is already a maxi
then you apply maxi fir here so now
these three will be compared then six
will come here and it will go there
right and then you apply maxi fur here
if you apply maxi from here it is
already a maxi that is how it is done so
we are going to apply max-heap this heat
wave function max if a function from the
largest non leaf down to one right so we
have already seen it and you know how to
do it well now my question is what is
the time taken in order to finish this
off what is the total time taken so that
I know for this bill max-heap you might
think that in order to apply a max-heap
if the tree is of length n of height H
and what is the height of the tree log
in isn't it and you already know that a
maxi PA will take a maximum of order of
n and we are applying max it fell nearly
n times therefore you might think that
the time taken is or drop and log in
right so which is as good as actually
sorting the elements but then it can be
shown that it is not the time complexity
it is not the way to analyze it okay so
I will just show you how to analyze this
one let us say we have a tree like this
we need to know some few properties of a
complete binary tree okay now all these
leaves are of height H or of height zero
therefore one two three four five six
seven eight there are eight nodes which
are having a height zero isn't it and
then all these nodes one two three four
there are four nodes which are having a
height one and then these two there are
two nodes which are having a high - all
right and there is one node which is
having a height three and what is the
total height of the tree three there is
an insight of the height of the root is
three right now first thing is you
should observe how many nodes of height
H can be present in a complete binary
tree so if I have a complete binary tree
then inside that how many nodes will be
at height H it can be proved that if
there are n nodes in the tree then n
divided by 2 power H plus 1 ok so it can
be seen that if I have a tree with n
nodes then M divided by 2 power H plus 1
nodes will be of height H is added
series now in this case how many nodes
are of 5 0 so what is total n here total
number of nodes in this tree or 15 right
15 divided by 2 to the power 0 plus 1 at
most these many nodes will be present of
height 0 then what is it 15 divided by 2
which is nothing but seven point five
seven point five ceiling state got it so
number of nodes of height zero or eight
at most eight I mean it need not be
eight if it is complete it is fine if it
is incomplete I mean it is almost
complete binary tree you know you might
not have these two which means I am
saying the maximum number of nodes of
height H will be
these many n by 2 power H plus 1 all
right what about number of nodes of
height 1 then we have to put a 15
divided by 2 power 1 plus 1 this will
give you the maximum number of nodes
that could be present in any complete
binary tree with a maximum with a height
of 4 1 all right then what is it
15 divided by 4 right then what you get
3 point something then we are going to
get 4 therefore 4 nodes will be present
of height 1 now let us see how many
nodes are present of height 2 2 plus 100
which is nothing but 15 divided by 8 so
we get 1 point something flow this see
leaves 2 therefore 2 nodes will be
present of height H how fighter to then
how many nodes will be present of height
315 divided by 2 power 3 plus 1 which is
nothing but 15/16 so we get 1 1 node is
that so whatever numbers are given you
here they are the at most therefore
number of nodes that could be present in
a complete binary tree are almost
complete binary tree of height H could
be maximum of this much so they are not
going to increase beyond that ok so that
one you should remember right so now we
got that the number of nodes of height H
could be a maximum of n by 2 power H
plus 1 in a heap why he PJ almost
complete binary tree right and next
thing is if I apply Mac simplified if I
apply a maxify procedure at any level
then to any node what is the maximum 100
what is the time taken by the max it 5
that is equal to the height of the node
see if you apply a maxify at this level
then the number of comparisons and
things required will be order of the
height isn't it therefore if I apply at
this level max if I will take order of
one time if I apply this let this level
max if I will take order of two time if
I applied this level it will take water
of three time in general if I apply
maxify to any node of height H then the
time taken will be order of H right
therefore we are going to apply
max-heapify on all the nodes let us say
we are even applying on the Leafs
actually we are not applying on the
leaves because leaves are already heaps
even if you assume that we are applying
on all the nodes including the leaves
then what will be the total work done is
so at every at a height H the work done
in order to know number of nodes of
height H will be these many then work
done by the max max heap if I apply max
upon all these nodes is this into order
of H why these many nodes are present at
height H and if I apply a max-heap on
any of these nodes the work done will be
order of H therefore total work done by
D or the total time taken by the Maxie
procedure is this much if I apply max
heap on all the nodes of height H and in
a tree a height the height can range
from height can range from 0 to login
right this is the total time see there
is necess our our max if is not going to
you know apply we are not going to apply
a max if always from the root we are
going to apply maxi from this and then
this this this and we are going to
slowly grow right therefore work done to
apply max upon this level is lesser and
then work done to applied at this level
is lesser than this level therefore work
done by the max heap is not actually
login at every node you know it is
depending on the height of that node
therefore if I have these many nodes of
height H that the total time are taken
by the max max heap if I algorithm is
this much right and that height can
range from 0 to n isn't it then you
could even write it as instead of this 2
power h plus one you can even write it
as into two isn't it and now order of
wish could be written as some constant
into H right therefore this is the total
time taken now you can see that n 2 and
C are constants therefore I could pull
them out so n 2 and C are constants if I
pull them out then I will get CN by 2
outside then Sigma H equal to 0 to login
H by 2 power H all right so actually we
are not applying this algorithm on the
whenever height H equal to 0 I know I am
just enough for the sake of completion
in a we should actually write height H
equal to 1 to n but then what is
happening is even if you write 0 that it
is not going to hurt anything because it
is going to be 0 right now this is order
of instead of stopping at login I can go
to infinity the reason is I have a
result there so H equal to 0 to infinity
see I am going to instruct it or stopped
at login but then I will go to infinity
then I will write H by 2 H definitely
this factor is greater than this factor
therefore I am putting order of which
means so definitely this factor is
greater than this factor therefore I am
putting less than or equal to now it is
it can be pruned that so this is a
harmonic progression if you take a
harmonic progression and you apply
integration and differentiation we are
going to get the result that this could
be equal to 2 so for this proof you
please refer to Corman book in that
Corman book appendix a dot 8 there is a
prove that this entire number is nothing
but 2 therefore if I put substitute 2
here I get the time complexity as order
of M right so whatever it is I mean to
prove that the time taken by the math
build a maxi piece order of M then it is
not actually order of n log n therefore
in order to build a maxim we are going
to have a time of order of M right from
scratch if the annoy if the entire area
is not at all following heap property
then if you have to build it from
scratch the total time taken will be
order of 4m how did I prove it first
thing is number of nodes at a level H in
a complete binary tree or a max if I
mean almost complete binary tree which
means a heap is n by 2 power H plus 1
right and then the work done by the
maxify at every level or at every node
is different and that differs with
respect to height if the height is
increasing definitely work done is going
to increase if the height is decreasing
work done is going to decrease but
whatever it is the work done is order of
H ok so using this proof we have seen
that the time taken by this one is order
of M then what about the space
complexity so we are going to call max
if one by one isn't it
therefore the space complexity required
will be displaced complexity taken by
max here at max and we have already seen
that max if is going to take a space
complexity of order of log n finally
when the max if is called max if ax is
called at the fruit then it is going to
take order of log N and all the other
function calls are not going to take
order of I mean they are going to take
less than log and only and moreover this
function call is made one after the
other therefore the total time space
complexity required by this built max
heap is equal to the maximum space
complexity taken by any of the maxi
prime which is nothing but order of log
N and when is that going to happen
whenever you call max if I on the root
not it so space complexity is order of
log N and time complexity is order of n
so in order to build a heap right we do
not need extra memory we just need a
stack which will be of size log in and
we need a time of order of n ok now we
shall see how to apply this heap
this heap data structure in order to do
the heapsort
containing and elements okay so what is
the total total time required or how to
build a max-heap
so I have already shown you that we are
going to use a Mac cp5 function which
I've just shown you so using the max if
a function we can build a heap as I will
show you how to do it with an example we
already seen it anyways right let the
example live like this
okay now you just see what is the
complete variety representation of this
so if I try to write it in a form of
almost binary tree we are going to get
this
I think this market one two three four
one two three four eight elements right
now one thing is how this algorithm is
going to work is initially a dot heap
size equal to a dot length it is assumed
that by the end of this procedure we are
going to make a dot heap size equal to a
dot length therefore it is setting now
if there are eight elements it is saying
that heap size is going to be eight so
why do we need that eight is inside this
heap we are always going to check Mac
simplify we are always going to check
whether element is having a left child
or not let us say we have read this
index then this is having left child but
it is not having right child just to
know that this right child is not there
we should set the heap size to be 8
otherwise what happens is it will try to
refer to 9 again and now for loop this
for loop is running from a dot length by
2 down to 1 the reason is this if I have
8 elements I have already shown you that
the leaves will run from 8 by 2 plus 1
to 8 so what is 8 by 2 plus 1 5 to 8
right so the leaves are 1 2 3 4 starts
from 5 5 6 7 8
therefore leaves are going to run from 5
6 7 8 right so that is what is the
meaning of this and what about the non
leaves 1 2
n by 2 1 to N by 2 or the non leaves and
then n by 2 plus 1 to N or the news
isn't it so these are the non leaves and
these are the leaves right so we have to
go to every non leaf one by one but then
we have to start from the largest index
that is why it is going to start from
largest index and we are going to apply
the heapify which means what is the
first largest you know non leaf for
therefore applied heapify here if I
apply heapify here then three will come
here and 0 will go there because you are
doing max-heapify and then we had
applied hipfire at three from four three
two one that is the way right if I apply
maxify here then it is already a maxi
then you apply maxi fir here so now
these three will be compared then six
will come here and it will go there
right and then you apply maxi fur here
if you apply maxi from here it is
already a maxi that is how it is done so
we are going to apply max-heap this heat
wave function max if a function from the
largest non leaf down to one right so we
have already seen it and you know how to
do it well now my question is what is
the time taken in order to finish this
off what is the total time taken so that
I know for this bill max-heap you might
think that in order to apply a max-heap
if the tree is of length n of height H
and what is the height of the tree log
in isn't it and you already know that a
maxi PA will take a maximum of order of
n and we are applying max it fell nearly
n times therefore you might think that
the time taken is or drop and log in
right so which is as good as actually
sorting the elements but then it can be
shown that it is not the time complexity
it is not the way to analyze it okay so
I will just show you how to analyze this
one let us say we have a tree like this
we need to know some few properties of a
complete binary tree okay now all these
leaves are of height H or of height zero
therefore one two three four five six
seven eight there are eight nodes which
are having a height zero isn't it and
then all these nodes one two three four
there are four nodes which are having a
height one and then these two there are
two nodes which are having a high - all
right and there is one node which is
having a height three and what is the
total height of the tree three there is
an insight of the height of the root is
three right now first thing is you
should observe how many nodes of height
H can be present in a complete binary
tree so if I have a complete binary tree
then inside that how many nodes will be
at height H it can be proved that if
there are n nodes in the tree then n
divided by 2 power H plus 1 ok so it can
be seen that if I have a tree with n
nodes then M divided by 2 power H plus 1
nodes will be of height H is added
series now in this case how many nodes
are of 5 0 so what is total n here total
number of nodes in this tree or 15 right
15 divided by 2 to the power 0 plus 1 at
most these many nodes will be present of
height 0 then what is it 15 divided by 2
which is nothing but seven point five
seven point five ceiling state got it so
number of nodes of height zero or eight
at most eight I mean it need not be
eight if it is complete it is fine if it
is incomplete I mean it is almost
complete binary tree you know you might
not have these two which means I am
saying the maximum number of nodes of
height H will be
these many n by 2 power H plus 1 all
right what about number of nodes of
height 1 then we have to put a 15
divided by 2 power 1 plus 1 this will
give you the maximum number of nodes
that could be present in any complete
binary tree with a maximum with a height
of 4 1 all right then what is it
15 divided by 4 right then what you get
3 point something then we are going to
get 4 therefore 4 nodes will be present
of height 1 now let us see how many
nodes are present of height 2 2 plus 100
which is nothing but 15 divided by 8 so
we get 1 point something flow this see
leaves 2 therefore 2 nodes will be
present of height H how fighter to then
how many nodes will be present of height
315 divided by 2 power 3 plus 1 which is
nothing but 15/16 so we get 1 1 node is
that so whatever numbers are given you
here they are the at most therefore
number of nodes that could be present in
a complete binary tree are almost
complete binary tree of height H could
be maximum of this much so they are not
going to increase beyond that ok so that
one you should remember right so now we
got that the number of nodes of height H
could be a maximum of n by 2 power H
plus 1 in a heap why he PJ almost
complete binary tree right and next
thing is if I apply Mac simplified if I
apply a maxify procedure at any level
then to any node what is the maximum 100
what is the time taken by the max it 5
that is equal to the height of the node
see if you apply a maxify at this level
then the number of comparisons and
things required will be order of the
height isn't it therefore if I apply at
this level max if I will take order of
one time if I apply this let this level
max if I will take order of two time if
I applied this level it will take water
of three time in general if I apply
maxify to any node of height H then the
time taken will be order of H right
therefore we are going to apply
max-heapify on all the nodes let us say
we are even applying on the Leafs
actually we are not applying on the
leaves because leaves are already heaps
even if you assume that we are applying
on all the nodes including the leaves
then what will be the total work done is
so at every at a height H the work done
in order to know number of nodes of
height H will be these many then work
done by the max max heap if I apply max
upon all these nodes is this into order
of H why these many nodes are present at
height H and if I apply a max-heap on
any of these nodes the work done will be
order of H therefore total work done by
D or the total time taken by the Maxie
procedure is this much if I apply max
heap on all the nodes of height H and in
a tree a height the height can range
from height can range from 0 to login
right this is the total time see there
is necess our our max if is not going to
you know apply we are not going to apply
a max if always from the root we are
going to apply maxi from this and then
this this this and we are going to
slowly grow right therefore work done to
apply max upon this level is lesser and
then work done to applied at this level
is lesser than this level therefore work
done by the max heap is not actually
login at every node you know it is
depending on the height of that node
therefore if I have these many nodes of
height H that the total time are taken
by the max max heap if I algorithm is
this much right and that height can
range from 0 to n isn't it then you
could even write it as instead of this 2
power h plus one you can even write it
as into two isn't it and now order of
wish could be written as some constant
into H right therefore this is the total
time taken now you can see that n 2 and
C are constants therefore I could pull
them out so n 2 and C are constants if I
pull them out then I will get CN by 2
outside then Sigma H equal to 0 to login
H by 2 power H all right so actually we
are not applying this algorithm on the
whenever height H equal to 0 I know I am
just enough for the sake of completion
in a we should actually write height H
equal to 1 to n but then what is
happening is even if you write 0 that it
is not going to hurt anything because it
is going to be 0 right now this is order
of instead of stopping at login I can go
to infinity the reason is I have a
result there so H equal to 0 to infinity
see I am going to instruct it or stopped
at login but then I will go to infinity
then I will write H by 2 H definitely
this factor is greater than this factor
therefore I am putting order of which
means so definitely this factor is
greater than this factor therefore I am
putting less than or equal to now it is
it can be pruned that so this is a
harmonic progression if you take a
harmonic progression and you apply
integration and differentiation we are
going to get the result that this could
be equal to 2 so for this proof you
please refer to Corman book in that
Corman book appendix a dot 8 there is a
prove that this entire number is nothing
but 2 therefore if I put substitute 2
here I get the time complexity as order
of M right so whatever it is I mean to
prove that the time taken by the math
build a maxi piece order of M then it is
not actually order of n log n therefore
in order to build a maxim we are going
to have a time of order of M right from
scratch if the annoy if the entire area
is not at all following heap property
then if you have to build it from
scratch the total time taken will be
order of 4m how did I prove it first
thing is number of nodes at a level H in
a complete binary tree or a max if I
mean almost complete binary tree which
means a heap is n by 2 power H plus 1
right and then the work done by the
maxify at every level or at every node
is different and that differs with
respect to height if the height is
increasing definitely work done is going
to increase if the height is decreasing
work done is going to decrease but
whatever it is the work done is order of
H ok so using this proof we have seen
that the time taken by this one is order
of M then what about the space
complexity so we are going to call max
if one by one isn't it
therefore the space complexity required
will be displaced complexity taken by
max here at max and we have already seen
that max if is going to take a space
complexity of order of log n finally
when the max if is called max if ax is
called at the fruit then it is going to
take order of log N and all the other
function calls are not going to take
order of I mean they are going to take
less than log and only and moreover this
function call is made one after the
other therefore the total time space
complexity required by this built max
heap is equal to the maximum space
complexity taken by any of the maxi
prime which is nothing but order of log
N and when is that going to happen
whenever you call max if I on the root
not it so space complexity is order of
log N and time complexity is order of n
so in order to build a heap right we do
not need extra memory we just need a
stack which will be of size log in and
we need a time of order of n ok now we
shall see how to apply this heap
this heap data structure in order to do
the heapsort
About this Video
4.79/5
Rating
Oct 06, 2025
Last updated
Related Exams
Build Max Heap Algorithm and Analysis, Programming and Data Structures, CSE, GATE for Computer Science Engineering (CSE)2025 is part of Computer Science Engineering (CSE) preparation. The notes and questions for Build Max Heap Algorithm and Analysis, Programming and Data Structures, CSE, GATE
have been prepared according to the Computer Science Engineering (CSE) exam syllabus. Information about Build Max Heap Algorithm and Analysis, Programming and Data Structures, CSE, GATE covers all important topics
for Computer Science Engineering (CSE)2025 Exam. Find important definitions, questions, notes, meanings, examples, exercises
and tests below for Build Max Heap Algorithm and Analysis, Programming and Data Structures, CSE, GATE.
Introduction of Build Max Heap Algorithm and Analysis, Programming and Data Structures, CSE, GATE in English is available as part of our Computer Science Engineering (CSE) preparation & Build Max Heap Algorithm and Analysis, Programming and Data Structures, CSE, GATE in Hindi
for Computer Science Engineering (CSE) courses. Download more important topics, notes, lectures and mock test series for Computer Science Engineering (CSE) Exam by
signing up for free.
Description
Video Lecture & Questions for Build Max Heap Algorithm and Analysis, Programming and Data Structures, CSE, GATE Video Lecture - Computer Science Engineering (CSE) - Computer Science Engineering (CSE) full syllabus preparation | Free video for Computer Science Engineering (CSE) exam.
Information about Build Max Heap Algorithm and Analysis, Programming and Data Structures, CSE, GATE
Here you can find the Build Max Heap Algorithm and Analysis, Programming and Data Structures, CSE, GATE defined & explained in the simplest way possible. Besides explaining types of Build Max Heap Algorithm and Analysis, Programming and Data Structures, CSE, GATE
theory, EduRev gives you an ample number of questions to practice Build Max Heap Algorithm and Analysis, Programming and Data Structures, CSE, GATE tests, examples and also practice Computer Science Engineering (CSE) tests.
Related Searches
CSE
,Summary
,video lectures
,shortcuts and tricks
,ppt
,MCQs
,Programming and Data Structures
,mock tests for examination
,Exam
,CSE
,Objective type Questions
,Semester Notes
,Viva Questions
,Important questions
,practice quizzes
,Sample Paper
,GATE Video Lecture - Computer Science Engineering (CSE)
,Free
,Programming and Data Structures
,past year papers
,Build Max Heap Algorithm and Analysis
,GATE Video Lecture - Computer Science Engineering (CSE)
,study material
,CSE
,Programming and Data Structures
,Build Max Heap Algorithm and Analysis
,Extra Questions
,GATE Video Lecture - Computer Science Engineering (CSE)
,Previous Year Questions with Solutions
,Build Max Heap Algorithm and Analysis
;
Study Build Max Heap Algorithm and Analysis, Programming and Data Structures, CSE, GATE on the App
Students of Computer Science Engineering (CSE) can study Build Max Heap Algorithm and Analysis, Programming and Data Structures, CSE, GATE alongwith tests & analysis from the EduRev app,
which will help them while preparing for their exam. Apart from the Build Max Heap Algorithm and Analysis, Programming and Data Structures, CSE, GATE,
students can also utilize the EduRev App for other study materials such as previous year question papers, syllabus, important questions, etc.
The EduRev App will make your learning easier as you can access it from anywhere you want.
The content of Build Max Heap Algorithm and Analysis, Programming and Data Structures, CSE, GATE is prepared as per the latest Computer Science Engineering (CSE) syllabus.
|
© EduRev
|
Education Revolution
|
|
Signup on EduRev and stay on top of your study goals
10M+ students crushing their study goals daily