English subtitles

← Remove Min - Intro to Algorithms

Get Embed Code
3 Languages

Showing Revision 3 created 05/25/2016 by Udacity Robot.

  1. The whole point of building up all this heap based technology
  2. is to allow us to do two things efficiently.
  3. One is getting and removing the min and the other one is inserting new elements into the heap.
  4. We like both of these to run in log n time, and if they are, then we can use them
  5. in the top k scenario that I was describing before.
  6. Finding the min is really easy right as the tippe top of the tree.
  7. In fact, getting the min done--easy, constant time.
  8. The problem is if where going to remove the min, look what happens.
  9. There's a sort of gaping volcanic hole at the top. Whatever will we do to fix this.
  10. We kind of have broken our big nice heap into two small nice heaps,
  11. but really want them to be one nice heap, so what can we do.
  12. Well, it would be nice if we had some kind of node someplace
  13. that we could fill in here and then maybe down heapify it.
  14. The natural place to get that node though is right there. The very last element to the heap.
  15. It some value, actually popping it off there doesn't cause any damage to the heap.
  16. We can move it to the tippy top and run down heapify.
  17. Once that concludes in about log in time, we've got our self a heap again. We're back in business.
  18. The steps were, remove the L zero node, copy the last node to the tippy top,
  19. then run down heapify on this no slightly smaller heap, write it fully.
  20. I've got n-1 elements in it now, but we run down heapify it on it
  21. and re-established heap property and we are done.
  22. Log n time. I want you to write some Python code to actually do this to remove min.
  23. It's only a couple of lines long.
  24. We'll give you down heapify and the build heap algorithm so that you can take a list,
  25. create a heap out of it and then remove the min from it.