Heaps 1 Introduction and Tree levels

so the first of the tree structures that we're going to talk about is kind of not really a tree sort of is but it it's sort of isn't kind of it's it's a heap and there's two types of heaps and there are there's two rules depending on which type of heap you use you can either follow the rule that the parent is greater than the children or you can follow the rule that the parent is less than the children okay those are the only two rules and so you just have to choose one so this is a max-heap and this is a min eat okay so if we have some numbers on our heap if we have some numbers on a heap the only rule is that the parent is always greater than the children it doesn't matter whether a node on one side is bigger than a node on the other side okay in a you know heap or the only rule is that the parent is bigger than a church or children or that the parent is smaller than the children okay so we've got a min heap and in a min heap the smallest values on top and in a max heap the largest values on top it doesn't matter which one you use and it's obviously very easy to change you just change a greater than to a less than or vice versa it doesn't matter which one you use depending on what you want to use it for okay presumably you want to do this so that you've got some data structure where you've got the smallest value on the top or the largest value on the top and so it's kind of up to the downstream application depending on whether you're going to use a max heap or a min heap let's have a look at the height let me just improve this mini this max heap a little bit so that we actually keep things on about the same level if there we go here's our max heap now notice that in our max heap actually in any heap in any tree on this level we have one element okay on this level we've got one from the root plus these two so three things on level two we've got these four plus these three so we've got seven and then on the next level down we've got a total of fifteen items remember when I was numbering the tree in the traversals we always ended up on 15 so this is N and this is for example the level 0 1 2 3 or we can talk about the height of the tree and the height of the tree is the number of edges on the longest path from the root to the leaf so the height of the tree here is zero the height of the tree is one hind the tree is to the hi Lauri is three okay and then if we calculate log base two of n plus one and we're going to subtract one from that n plus 1 is 2 log base 2 of 1 minus 1 is 0 when n is 3 n plus 1 is 4 log base 2 of 4 is 2 oops go subtract 1 2 minus 1 is 1 when n is 7 7 plus 1 is 8 log base 2 of 8 is 3 minus 1 is 2 when n is 15 and plus 1 is 16 log base 2 of 16 is 4 minus 1 is 3 okay so if we know how many elements we have in our tree we can calculate having the height of the tree the number of levels in the tree

Channel: RobEdwards

Views: 17,533

Rating: 4.9248824 out of 5

Keywords: data structures, computer science, cs310

Id: BzQGPA_v-vc

Length: 5min 44sec (344 seconds)

Published: Thu Nov 10 2016