میانه‌روی

Main.py

import heapq
maxHeap = [] # elements before median and median -> max element in maxHeap is median
minHeap = [] # elements after median
# |maxHeap[0]| is always maximum element
# minHeap[0] is always minimum element
# heapq is min-heap so for max-heap we multiply elements by -1



q = int(input())
for i in range(q):
    x = int(input())

    heapq.heappush(maxHeap, -x) # add -x to maxHeap

    # add maxElement of maxHeap to minHeap
    maxElement = heapq.heappop(maxHeap)
    maxElement *= -1 # we store -maxElement in maxHeap
    heapq.heappush(minHeap, maxElement)

    # add minElement of minHeap to maxHeap
    minElement = heapq.heappop(minHeap)
    minElement *= -1 # we want to store -minElement to maxHeap
    heapq.heappush(maxHeap, minElement)

    # balance size of heaps
    # note len(minHeap) is always equal to len(maxHeap) or len(maxHeap)-1 or len(maxHeap)-2
    if len(maxHeap) > len(minHeap) + 1 :
        x = heapq.heappop(maxHeap)
        x *= -1
        heapq.heappush(minHeap, x)

    median = heapq.heappop(maxHeap)
    heapq.heappush(maxHeap, median)

    print(-median)