A min-heap

Write a min-heap class stored in a Python list (lessons 1 and 2). push(x) adds a value, pop() removes and returns the smallest value, peek() returns the smallest value without removing it, and len(h) gives the number of values.

h = MinHeap()
h.push(5); h.push(3); h.push(8)
h.peek()     # 3
h.pop()      # 3
h.pop()      # 5
len(h)       # 1

Values can repeat. The tests never call pop or peek on an empty heap.

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).

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 30,000 values. push and pop should take O(log n) time and comparisons.