Heaps in 3 minutes — Intro

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.