English subtitles

← Inserting Elements - Intro to Algorithms

Get Embed Code
3 Languages

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

  1. So the last thing I promised I would tell you about
  2. is inserting elements into a heap.
  3. And that turns out not to be all that hard,
  4. but it does involve some coding that we haven't done yet.
  5. The idea is that the new element that we're going to insert
  6. we stick at the sort of bottom right corner of the heap.
  7. Or, if the heap was already full, then the far left.
  8. But now we have potentially violated the heap property,
  9. so this node to it's parent could be problematic.
  10. So, essentially, we need to do
  11. some sort of an analog of down-heapify that I call up-heapify
  12. that takes this value that might be problematic,
  13. swaps it up if it is,
  14. and then continues to swap it up the tree
  15. until it reaches a place where it is smaller than both of its children.
  16. At which point, the heap property is satisfied globally.
  17. So I'm going to leave that as a homework problem for you
  18. to actually code up-heapify,
  19. and that gives us the insert that we need.
  20. So now that we can insert and delete into heaps and (logn) time,
  21. we can use this to solve the TopK problem
  22. that we've been talking about throughout this unit.
  23. By running through the list of the N elements that we want the TopK of,
  24. and meanwhile we keep a heap of size K off to the side,
  25. and so we're trying to the largest K, in this case.
  26. So each new element that we encounter
  27. we ask, is this element bigger than the smallest
  28. value that we've kept so far?
  29. So does it deserve to be in the TopK so far?
  30. If not, we can just throw it away,
  31. because we know it's not going to be part of the TopK.
  32. If it is, then the smallest thing in that heap
  33. no longer needs to be there, because we found something better.
  34. So we delete min,
  35. and we insert the new value that we just got into the heap
  36. and reestablish the heap property
  37. by--well, we could do it as a down-heapify, actually,
  38. because we deleted the node from the top.
  39. We can replace it with something else.
  40. So, for each of N times,
  41. we do possibly one insert into the heap,
  42. which is a log K operation.
  43. So the total running time ends up being we do (nlogk) operations.
  44. So that's actually pretty efficient.
  45. It doesn't solve the TopK problem better
  46. than the randomized algorithm we talked about--
  47. the partitioning algorithm--
  48. but it does it pretty fast
  49. and there's other uses for this.
  50. We'll see that in the next unit.
  51. Thanks a lot, and good luck with the homework.