Level 3 · Structures
Free Heaps lessons
8 lessons, about 100 minutes in all. Each teaches one idea with a visual, then gives you one problem built for it. Read the lessons here, then create a free account to solve the problems and keep your progress.
Stage 0Smallest first
- Extract smallest elementsUse a min-heap to repeatedly extract the smallest available item in logarithmic time.8 min
- Connect ropesRepeatedly combine the two shortest ropes to minimize cumulative connection cost.8 min
- Last stone weightRepeatedly smash the two heaviest stones using a max-heap until at most one remains.8 min
- Reduce largest pilesRepeatedly find the maximum pile and replace it with its integer square root.8 min
Stage 1Top k
- The kth biggest valueFind the kth largest value of an array by keeping a small min-heap that holds only the k biggest values seen so far.14 min
- The k most common valuesFind the k values that occur most often, by counting each value and keeping a small heap of the most frequent counts.16 min
- The points nearest the originPick the k points closest to the origin from a long list, by keeping a max-heap of the k closest points seen so far and removing the farthest whenever it grows.16 min
- Tasks that need a cool-downFind the shortest time to finish a list of tasks when the same kind of task must wait n time units between runs, by always running the task with most work left.22 min
There’s more after this
These are the opening stages of Heaps. The full path climbs on to harder problems and a mastery test. Create a free account and we’ll keep your place.
Start the full path free