Description

Two heap solves the issue that a heap can only be max or min. With two heap we can find the median.
?

Reach for when

You need to repeatedly get the middle value of a constantly updating array.

Runtime

add: O(log(n))
get median: O(1)

Visualization

Two heap-1784053270625.webp717
Two heap-1784053356148.webp720
Two heap-1784053380971.webp718

Pseudocode

Keep two heaps: a MAX-heap for the smaller half, a MIN-heap for the larger half.

To add a number:
	- put it in the lower half
	- move the lower half's biggest over to the upper half   (keeps every low <= every high)
	- if the upper half is now bigger, move its smallest back (rebalance the sizes)

To get the median:
	- heaps unequal size -> median is the top of the bigger one
	- heaps equal size   -> median is the average of the two tops

Code

import heapq

low = []
high = []

def add(x):
	heapq.heappush(low, -x)
	heapq.heappush(high, -heapq.heappop(low))
	if len(high) > len(low):
		heapq.heappush(low, -heapq.heappop(high))

def median():
	if len(low) > len(high):
		return -low[0]
	return (-low[0] + high[0]) / 2