today we're going to learn about heaps you often hear the word heap when discussing
storage for garbage collection in languages such as java but this video is about the heap data
structure that is used to manage information heaps are sometimes called binary heaps
and are nearly complete binary trees here's an example of a heap by a nearly complete
binary tree i mean that all levels are filled except the lowest and the lowest level is filled
up to a certain point starting from the left uses of heaps include heap sort and priority
cues and there are two kinds of heaps max heaps and min heaps on the left
we have a max heap the condition for a max heap is that the value of the node i is
less than or equal to the value of its parent max heaps are used for heap sort similarly for the min heap the value of the node i is greater than or equal
to the value of its parent min heaps are great for priority queues because we said heaps are nearly complete
binary trees we know that the height of a heap is big o of log n which you'll see in
various operations that we'll learn later i'd also like to show heaps
represented as an array here's our max heap and here it is as an array the root of the tree is at index 1 of the array to get a node's left child you
simply take the index times by 2 and to get the notes right child you
take the index times by two and add one finally to retrieve a node's parent it's the floor
of the node's index divided by two we choose to put the root at index 1 instead of 0 as it keeps
this arithmetic cleaner and most computers can do these operations with fewer instructions
let's take a look at 15 which is at index 3. the left child of 15 is equal to 2 times 3
which is the sixth index and a node value of 12.
the right child of 15 is 2 times 3 plus
1 which is the index of 7 or the node 13. lastly the parent of 15 is the floor of 3 divided by 2 which is the first
index and the root of our tree 21. you know i prefer brevity
so we'll end the video here and in the next one i'll show you how to create a
heap from an unordered array thanks for watching.