0:05

What is particularly easy for

Â binary max heaps is finding the maximum value without extracting it.

Â I mean, it is easy to implement GetMax operation.

Â Well, recall that the main property of that binary max heap tree is the following.

Â For each edge its top value is greater or equals than its bottom value.

Â this means that if we go from bottom to top now in our trees, the

Â values can only increase.

Â This in particular means that the maximum value is stored at the root of our tree.

Â So just to implement GetMax,

Â we just return the value at the root of our tree.

Â And this takes us just a constant time of course.

Â Now let see how inserting a new element into to the max binary heap works.

Â So first of all a new element should be attached somewhere to our tree.

Â We cannot attach it to the root in this case for

Â example, because the root already has two children.

Â Therefore, we just attach it to some leaf.

Â Let's select for example, the leaf seven and attach a new node to it.

Â The new node in this case has value 32.

Â Well, it is still a binary tree.

Â Right? Because seven, before attaching seven,

Â had zero children, now it has just one child.

Â So it is still a binary tree.

Â However, the heap property might potentially be violated.

Â And it is violated actually in this case, right?

Â Which is shown by this red edge.

Â So for this red edge the value of it parent which is seven,

Â is less than the value of its child which is 32.

Â So we need to fix it somehow.

Â So to fix it we just allow that the new element to sift up.

Â So this new element has value 32,

Â which is relatively large with respect to all other elements in this tree,

Â so we need to move it somewhere closer to the root.

Â So the process of moving it closer to the roof is called sifting up.

Â 2:25

So the first thing to do is we need to fix this problematic edge.

Â To fix it, we perform the following simple operation.

Â We just swap the corresponding two elements.

Â In this case, we'll swap seven and 32.

Â After they swap, there is no problem on this edge.

Â However, it might be the case that the new element 32 is still smaller.

Â Is still greater than its parent and this is the case, in our toy example.

Â So the parent of 32 is now 29,

Â which is smaller than 32, so we still need to fix this red problem.

Â And we just repeat this process,

Â we again swap the new element with its parent, right?

Â So we swap it and now we see that the property is

Â satisfied for all edges in this binary tree.

Â 3:33

And what is important to note here is that we maintained the following invariant,

Â that the heap property at any point of time of sifting the new element up,

Â the heap property is violated on at most one edge of our binary tree.

Â So and if we see that there is a problematic edge,

Â we just swap its two elements, right?

Â And each time during this process the problematic node gets closer to the root.

Â This in particular implies that the number of swaps required is at most

Â the height of this tree.

Â Which in turn means that the running time of insertion procedure,

Â as well as the running time of the sifting up procedure,

Â in this case is big O of the tree height.

Â 4:24

Now let's see how the extract max procedure works for binary max heaps.

Â First of all, recall that we already know that the maximum value is stored

Â at the root of the tree.

Â However, we cannot just take and

Â detach the root node because it will leave two sub trees, right?

Â So we need to somehow preserve the structure of the tree.

Â What is easy to detach from a binary tree is any leaf.

Â So let's do the following, let's select any leaf of our tree and

Â let's replace the root with this leaf.

Â So in this case this produces the following tree.

Â 5:04

This potentially might violate the heap property.

Â And in this case, this does violate the property.

Â So the new root 12, is less than both its children.

Â So the property is violated on two edges.

Â So 12 is a relatively small number in this case.

Â So we need to move it down to the leaves.

Â Great, so for this we will implement a new procedure,

Â which is called SiftDown, okay?

Â So, similarly to SiftUp, we are going to replace,

Â 5:41

to replace the new element with one of its children.

Â In this case we have a choice actually,

Â we can replace it either with its left child or with its right child.

Â By thinking a little bit we realize that it will make

Â more sense to replace it with the left child in this case.

Â Because the left child is larger than the right child, because after this, after we

Â replace 12 with 29, the right problematic edge will be fixed automatically, right?

Â So this is how we are going to perform the SiftDown procedure.

Â Once again, we select the largest of two child and we replace.

Â the problematic node with this larger child.

Â As you can see, the right problematic edge is fixed automatically.

Â The left edge is also fixed, just because we swapped two elements.

Â However, the new problematic node might introduce new problems,

Â right closer to the bottom of the tree.

Â Now we see that there is still a problematic edge, so

Â in this case, we have just one edge so 12 is smaller than 14, but

Â it is greater than seven, so we are safe in the right tree.

Â In this case we swap 14 with 12 and

Â after that we just get a tree where the property is satisfied on all edges.

Â So once again we maintain the following invariant.

Â At each point of time we have just one problematic node, and

Â we always solve the problematic node.

Â With the larger one of its children, so that to fix both problematic edges.

Â Right? And

Â the problematic node always gets closer to the leaf,

Â which means that the total running time of the extract max as well as

Â the sift down procedures is proportional to the tree height.

Â 7:46

Now, when we have implemented both procedures, sifting up and sifting down,

Â it's not so difficult to implement also the ChangePriority procedure.

Â So assume that we have an element for

Â which we would like to change its priority.

Â This means that we are going either to decrease its priority or

Â increase its priority.

Â Well, to fix the potential problems that might be introduced

Â by changing its priority, we are going to call either sifting up or sifting down.

Â 8:16

Well, let me illustrate this again on the toy example.

Â Assume that we are going to change the priority of this leaf 12.

Â So we've just changed it.

Â We just increased the priority of this element to 35.

Â In this case, we potentially introduced some problems and we need to fix some.

Â 8:36

Well we see that 35 is a relatively large number which means that we need to

Â sift it up.

Â So we need to move it closer to the root.

Â So to do this we just call SiftUp procedure.

Â Which repeatedly swaps the problematic node

Â with its parent, so

Â in this case this will produce the following sequence of swaps.

Â 9:00

First will swap 35 with 18 this gives us the following picture,

Â we see there is still a problem 35 is still larger than its parent so we swap it again.

Â Now we see that 35 is smaller than its parent.

Â And actually, the heap property is satisfied for all edges.

Â Once again, what is important in this case is that at each point of time,

Â the heap property is violated on at most one edge of our tree.

Â So since our problematic node always gets closer to the root at each step,

Â I mean, after each swap.

Â We conclude that the running time of change priority procedure is also at most

Â Big O of the tree height.

Â There is an elegant way of removing an element from the binary max heap.

Â Namely it can be done just by calling two procedures that we already have.

Â So I assume that we have a particular element that we're going to remove.

Â 10:01

So the first step to do is we just change its priority to plus infinity, that is,

Â to a number which is definitely larger than all the elements in our binary MaxHeap.

Â When we call it, the change priority procedure will sift this element

Â to the top of our tree, namely to the root of our tree.

Â Then to remove this element it is enough to call the extract max procedure.

Â So in this particular example it will work as follows.

Â So assume that we're going to remove the element 18,

Â which is highlighted here on this slide.

Â So we first change it's priority to infinity.

Â Then the ChangePriority procedure calls the SiftUp procedure.

Â This procedure realizes that there is, that the property is violated on this edge.

Â And swaps these two elements.

Â Then it swaps the next two elements and each at this point well this,

Â 11:04

this node that we're going to remove is at the root.

Â Well, to remove this node, we just call the ExtractMax procedure.

Â So recall that the first step of ExtractMax is to replace

Â the root node with any leaf.

Â So let's select, for example, 11.

Â So we replace, we replace the root with 11.

Â Then we need to call sift down, just to

Â let this new root go closer to the leaves.

Â 11:39

Well, in this case, 11 will be replaced first by 42,

Â then there is still a problem on the edge from 11 to, to 18.

Â So we swap 11 with 18 and finally we swap 11 with 12.

Â Well, once again since everything boils down just to two procedures.

Â First is change priority.

Â And the second one is extracting the max.

Â And they all, they both work in time proportional to the tree height.

Â So we conclude that the running time of the remove procedure is also, at most,

Â Big O of the tree height.

Â So to summarize, we were able to implement all

Â max binary heap operations in time proportional to the tree height, and

Â the GetMax procedure even works in constant time in our current implementation.

Â So we definitely would like to keep our trees shallow.

Â And this will be the subject of our next video.

Â