https://github.com/python/cpython/commit/dc05d475c149289749f6131e3c0c4c1d2c492c8e
commit: dc05d475c149289749f6131e3c0c4c1d2c492c8e
branch: main
author: Raymond Hettinger <[email protected]>
committer: rhettinger <[email protected]>
date: 2025-07-30T15:53:33-05:00
summary:
Add example of min-heap and max-heap working together (gh-137251)
files:
M Doc/library/heapq.rst
diff --git a/Doc/library/heapq.rst b/Doc/library/heapq.rst
index 462b65bc7afba4..95ef72469b18ef 100644
--- a/Doc/library/heapq.rst
+++ b/Doc/library/heapq.rst
@@ -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
-----------------------------------
_______________________________________________
Python-checkins mailing list -- [email protected]
To unsubscribe send an email to [email protected]
https://mail.python.org/mailman3//lists/python-checkins.python.org
Member address: [email protected]
