Where it runs
1. The problem
Step 81 gave you two moves. The first builds a heap from any array in one O(n) pass. The second takes the smallest value off the top. Heap sort (heapsort) is what you get when you take the minimum again and again until the heap is empty.
You have an array of numbers and need them in increasing order. You already know how to take the smallest number out of a heap quickly. Take it and write it down. Take the new smallest and write it down. Repeat. When the heap is empty, the numbers you wrote down are in order.
That is the whole method: no new data structure and no new comparisons. You take the heap you built and empty it. Heap sort costs O(n log n) even in the worst case. Its classic version sorts inside the original array and needs no memory for a second array. That is why it is chosen where memory is short and slow cases are not allowed.
This step is part of the paid track
The first 33 steps are open to everyone: lesson, exercise and tests. This one opens with full access. Start with a free account and the free steps.
Create a free accountSee what is includedOn LeetCode
Problems that need values in sorted order, or only the first few of them. Heap sort sorts in place in O(n log n) even in the worst case, and stopping after k pops gives the k smallest.
Heap sort passes with no recursion and no extra array, and never falls to n^2 the way a careless quick sort can.
Heapify pairs of soldier count and row index, then pop k times.
Heapify as a max-heap and pop twice, since a full sort is not needed for two values.