A renderer receives a whole batch of paint jobs at once, as an array of priorities. Pushing them into a heap one by one costs O(n log n); turning the array into a min-heap in place can be done in O(n).
Write heapify(values) that rearranges values in place into a min-heap using exactly this method, so the result is unique: for each index i from Math.floor(values.length / 2) - 1 down to 0, sift values[i] down. Sifting down means: while the value has a child smaller than it, swap it with its smallest child (the left one if the two children are equal), and continue from the child's index. The function doesn't need to return anything.
Input: values = [5,3,8,1] Output: [1,3,8,5]
First index 1 (3) swaps with its child 1. Then index 0 (5) swaps with 1, and then with 3.
Input: values = [1,2,3] Output: [1,2,3]
It is already a min-heap, so nothing moves.
0 <= values.length <= 10^5-10^9 <= values[i] <= 10^9Run tries your code on the examples. Submit runs every test, including hidden edge cases, and solves the problem when they all pass.
Ctrl + Enter runs, Ctrl + Shift + Enter submits (⌘ on a Mac).
I'm here to help with #380 Heapify a Render Queue. I give hints, never the solution, so you get to solve it yourself. Ask for a hint, select code to ask about it, or press Ask Tuto why on a failing test.
Your first 3 answers need no account. for free to keep asking.