Go Back
- Describe how to efficiently implement this algorithm using a binary heap.
- A binary heap can help me keep track of the bins with the most available space quickly. Every time I add an object, I can easily check which bin has the most room by looking at the top of the heap.
- When I place an object in a bin, I update that bin's available space and adjust its position in the heap. This ensures the bin with the most space is always on top for the next object.
- Analyze the runtime of this algorithm.
- The time it takes to run this algorithm depends on how many objects
n I have. For each object, I might need to update the heap. Since updating the heap can take some time (technically, logarithmic time), the total time gets bigger as I have more objects.
- The technical term for this is
O(n log n) time. It's like saying, for each object, I take a bit of time that grows a bit as the pile of objects grows.
- Show that this greedy algorithm does not always return the optimal solution.
- The greedy approach doesn't always give me the least number of bins. This is because it always looks for the best place for the current object without thinking about future objects.
- Imagine I have two objects, each just a little smaller than half the bin. The greedy method would put each in a separate bin, but I could actually fit both in one bin if I thought ahead. This example shows that the greedy method can waste space by not planning for what's coming up.