Build a heap in O(n)

Rearrange a list, in place, so that it becomes a min-heap: every a[i] is at least its parent a[(i - 1) // 2]. Change the list you are given and return nothing, as heapq.heapify does.

a = [5, 3, 8, 1, 9, 2]
heapify(a)
# a is now a min-heap, for example [1, 3, 2, 5, 9, 8]

Any arrangement that obeys the heap rule passes. The tests check the rule, not one exact list.

The heapq module is switched off for this problem: write the heap yourself. A heap is a plain list with sift up and sift down (lessons 1 and 2); you can copy your class from HEAP-P1.

One test passes in numbers that count how often they are compared with <, <=, > or >=. They behave like ordinary numbers otherwise. This is how the tests tell an O(log n) heap step from an O(n) scan, which a timer cannot always do.

Limits

• Up to 200,000 values. Use at most 3n comparisons: pushing the values one at a time is not fast enough.