Heapify and pop: build a heap all at once, then remove the min
Tier 1LockedWhere it runs
1. The problem
In step 80 you grew a heap one push at a time, and each new value climbed up (sift up). Now you already have a whole array of numbers, and you want it to become a heap in one go. You also want to keep taking the smallest value out.
You could push the numbers into an empty heap one by one. That works, but it costs O(n log n): n pushes, and each one can climb up to log n levels. There is a faster way: reorder the array you already have, in place, in O(n).
Once you have a heap, you need the other half too: take the smallest value out and leave a valid heap behind, so it can hand you the next smallest. Both jobs use one new move, the mirror image of sift up: sift down.
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
Simulation problems that take the biggest or smallest item many times and put a changed one back. Heapify the input in O(n), then each pop and push costs O(log n).
Heapify as a max-heap, pop the two heaviest, and push back the difference if it is not zero.
Heapify the piles as a max-heap, then k times pop the largest and push back its square root rounded down.
The same loop, removing half of the largest pile each time, with n and k up to 10^5, so sorting again every round is too slow.