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.