Hey guys, in this video I'm going to go over how to add and remove from heaps.
I'm going to use the example given here. As you can see, I have a binary heap. Each parent node can have
0, 1, or 2 children and this is also an example of a max heap.
If you look at the key values in each node, the parent node is always going to have a higher
value than either of the
children. And the--it doesn't matter if the left child is higher than the right child or vice versa. It just matters that the parent
is always greater than the children. Let's go ahead and get started. I'm going to do these operations
sequentially. The first one says to add 48. When you're going to add a node to a heap, you want to look for the
next available spot to add a leaf node. Heaps are complete binary trees,
so the last level--it doesn't have to be completely full--
but you have to fill it left to right. The next available leaf node to add would be here and we're going to add
48. Then basically what you do is just swap the values until it's in the correct position.
So 48 is going to end up here at the end and that means we're going to swap the 18
to go down here and the 25 to go here. That's going to be the new tree
And we're done with 48. We're going to do the same thing with 20. We're going to add it to the next available leaf
position. So that's here, and we don't have to push it up or do any swaps because 20 is less than 25.
We're done with that one. Next we're going to do 42. Again we look for the next left most leaf we can add, and it's going to be here.
We're going to swap 42 and 22 and then we're done with that. And the last one says 8.
For heaps, you can have duplicate values. Even though we already have an 8 here
we can add another 8 because duplicates are allowed. We add 8 and we're done with that one.
We're done with all the adding and now we're going to remove three times. When you remove from a heap tree,
you're going to always remove from the root node for max heaps because that's the highest value.
What you want to do
is, we're going to swap the root node and the rightmost leaf on the last
level and then we're going to
remove the leaf, which will have the highest value, and then push down
the swapped value of the leaf node. That means we're going to
say that the root is switched with the
last leaf. That's 8. And then this is going to be 50, and then we can just remove the 50
but now we have to push down 8 until it's in the correct position.
To push down, what you want to do is you want to compare the parent to its two children
and you want for max heaps to switch with the larger value, the bigger child.
We're going to swap 48 and 8, and that way we don't have to check that the
swap is bigger than the left-hand side because we already know it's going to be bigger than the other
child because we pick the bigger one. We swapped 48 and 8 and then we're going to do the same thing.
We look at the children node and we're going to swap 42 and 8 because 42 is bigger than 25.
And we do--well we only have one child here.
We're going to swap the 22 and the 8 and then that's our new
tree. It looks very ugly. Now you have to do this two more times. We're going to do the same thing.
We're going to swap 8 and 48 in order to be able to remove
48. We remove that and now we have to push down 8.
Forty-two is bigger than 10, so we're going to swap 8 and 42.
Twenty-five is greater than 22, so we're going to push up 25. And 20 is greater than 18,
so we're going to push up 20, and then that's our new heap. And we're going to do it one more time.
The same thing, we're going to swap 42 and 8. We're going to remove
42, and we're going to push down 8. We're going to
push up 25. Add 8 here and then swap with 22.
That's going to be our final tree and let me just write out what it would look like again.
It's going to be 25, 10, 22,
28,
18.
This is an ugly drawing
but this is what the tree or the heap will look like after
we have added four times and removed three times. And we're done with this problem.
*chiptune music*