Skip to content

Add example of minheap and maxheap working together #137251

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Merged
merged 1 commit into from
Jul 30, 2025
Merged

Add example of minheap and maxheap working together #137251

Changes from all commits
Commits
Show all changes
1 commit
Select commit
File filter

Filter by extension

Filter by extension
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
36 changes: 36 additions & 0 deletions Doc/library/heapq.rst
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -231,6 +231,42 @@ Heap elements can be tuples. This is useful for assigning comparison values
(1, 'write spec')


Other Applications
------------------

`Medians <https://en.wikipedia.org/wiki/Median>`_ are a measure of
central tendency for a set of numbers. In distributions skewed by
outliers, the median provides a more stable estimate than an average
(arithmetic mean). A running median is an `online algorithm
<https://en.wikipedia.org/wiki/Online_algorithm>`_ that updates
continuously as new data arrives.

A running median can be efficiently implemented by balancing two heaps,
a max-heap for values at or below the midpoint and a min-heap for values
above the midpoint. When the two heaps have the same size, the new
median is the average of the tops of the two heaps; otherwise, the
median is at the top of the larger heap::

def running_median(iterable):
"Yields the cumulative median of values seen so far."

lo = [] # max-heap
hi = [] # min-heap (same size as or one smaller than lo)

for x in iterable:
if len(lo) == len(hi):
heappush_max(lo, heappushpop(hi, x))
yield lo[0]
else:
heappush(hi, heappushpop_max(lo, x))
yield (lo[0] + hi[0]) / 2

For example::

>>> list(running_median([5.0, 9.0, 4.0, 12.0, 8.0, 9.0]))
[5.0, 7.0, 5.0, 7.0, 8.0, 8.5]


Priority Queue Implementation Notes
-----------------------------------

Expand Down
Loading