Max-Heap With Bulk Build and Replace

Implement a binary max-heap as a class MaxHeap, without using heapq. The largest value must always be at the root.

• MaxHeap(items) builds the heap from a list of integers (possibly empty). Build it in place in O(n) by fixing the sub-heaps from the last parent up to the root, not by pushing one value at a time.
• push(x) inserts x.
• pop() removes and returns the largest value, or None if the heap is empty.
• peek() returns the largest value without removing it, or None if the heap is empty.
• replace(x) removes and returns the largest value and inserts x in a single sift; on an empty heap it just inserts x and returns None.
• size() returns the number of stored values.

Examples

Input:  ops  = ["MaxHeap", "peek", "replace", "pop", "push", "pop", "pop", "size"]
        args = [[[4, 9, 2]], [], [7], [], [1], [], [], []]
Output: [None, 9, 9, 7, None, 4, 2, 1]
Explanation: the heap starts with {4, 9, 2}. replace(7) returns the old maximum 9 and
             leaves {4, 7, 2}. pop returns 7; after push(1) the pops return 4 and 2.

Constraints

• Up to 10**5 values overall, values in [-10**9, 10**9]
• Target complexity: constructor O(n); push, pop, replace O(log n); peek, size O(1).

Goals

• Build a heap from an arbitrary list in linear time with bottom-up sift-down
• Implement a max-heap directly instead of negating values
• Combine pop and push into a single replace operation