Python中实时整数流的中位数

假设您正在从文件或数组中读取数字，或者只是在一个数字流中输入数字，并且有源源不断的数字流入。必须确定在迄今为止看到的每个数字之间出现的那个数字。在这种情况下，当数据量不断累积时，我们所说的就是找到“中位数”。

这就像要求机器在您不断向列表中添加新数字时识别中间数字，因为您要与机器和机器学习打交道。挑战在于，即使这些值可能来自任何来源，例如记录或只是通过输入，相关的机器仍然必须确定中位数。

所以，简单来说，“运行整数中位数”意味着在一个不断到来的数字序列中找到中间数字，当数字没有按特定顺序到来时，这有点像一个谜题。

想象一下从源（如计算机应用程序）获取一系列数字。您试图找到迄今为止看到的所有数字的“中位数”。假设没有重复的数字会让事情变得简单。

例如，取一个数字序列，如 5、15、1、3。

在看到第一个数字 (5) 后，平均数只是 5，因为它只有一个数字。

读取第二个数字 (15) 后，您有两个数字 (5 和 15)，中位数是排序后中间的数字。所以，在这种情况下，中位数是 10（5 和 15 的平均值）。

当您读取第三个数字 (1) 时，您现在有三个数字 (5、15 和 1)。要找到中位数，您需要对它们进行排序并选择中间的数字，即 5。

当您分析最后一个数字 (3) 时，您会得到以下四个数字：5、15、1 和 3。分类后，您会得到 1、3、5 和 15。中位数是中间两个数字的平均值，即 4。

当您读取更多数字时，这个过程会继续。

根据您处理的是偶数个还是奇数个项目，这种边走边计算平均数的方法称为“在线算法”。它表明，即使您不知道增长中的所有值，您也可以计算中位数，这在各种情况下都很有用。

让我们立即讨论几种解决此问题的可能方法。

什么是中位数？

中位数是一种在数字组中找到中间点的方法。它帮助我们理解数据的分布。这就是我们确定它的方法：

奇数数量的文档：如果我们的集合具有非偶数个值，当我们按从大到小的顺序排列信息时，我们只需找到恰好位于中间的一个。那个中间数字就是我们的中位数。

如果偶数个标准中有两个数字恰好在中间，我们可以通过对这两个值取平均值来计算平均值。

总而言之，平均值向我们展示了数字组中“中间”位置的总体概念，并有助于理解一组事实。

示例 1

“最大堆”和“最小堆”这两个词指的是几种独特的数据结构，它们将有助于我们解决这个挑战。它们充当数字的分类容器，最大堆存储较大的数量，最小堆存储较小的数量。程序员可以利用 C++ 或 Python 中称为“priority_queue”的工具来生成最大堆和最小堆。

接下来，我们按步骤概述解决此问题的方法。

代码

输出

5
10.0
10
12.5
10

这段代码是为名为“Medians”的 Python 函数设计的。它们随后计算并显示一组值的当前中位数。它的工作方式如下：

1. 它首先导入一些需要使用堆的工具。可以将堆视为组织好的数字列表。
2. 然后，它定义了“Medians”函数，该函数接受两个输入：
3. 您想找到中位数的数字列表。
4. 该列表中元素的总数。
5. 它设置了两个空列表，称为“max”和“min”。这些列表将用于在我们遍历输入列表时跟踪最大和最小的数字。
6. 它使用“heapify”函数将这些空列表转换为正确的堆。本质上，它确保项目列表得到正确安排。
7. 它选择的第一个值来自您提供的信息，然后被称为其持续时间内的“中位数”。它还将此数字放入“max”堆中。
8. 它向您显示此初始中位数。
9. 然后，它开始逐一遍历输入列表中的其余数字。
10. 对于它遍历的每个数字：
11. 它计算“max”堆和“min”堆中值的总数量。
12. 如果“max”堆中有多余的数字，它会确定该特定值属于“max”组还是“min”组，并进行必要的调整。
13. 它将当前总数添加到其中一个垃圾箱中，并在两个垃圾箱中的数字数量相同时更改中位数。
14. 当“min”垃圾箱中有更多值时，它的行为与看到“max”堆中更大的数字时类似。
15. 在将当前显示的值放入适当的上下文并进行必要的调整后，它显示新的平均值。
16. 这个过程一直持续到它查看了输入列表中的所有数字为止。

简单来说，这段代码有助于查找数字列表中运行中的中位数。除了在分析每个值时更新和显示平均值外，它还会在处理整个列表时记录最大和最小的数字。这是一种有效的做事方法。

示例 2：插入排序

您是否曾考虑过如何确定数字数组中的中心数字？一种方法是使用称为“插入排序”的方法。当您收到卡片时，这就像浏览一副卡片。

假设您一次收到一个数字列表。插入排序允许您在接收数字时立即对其进行分类。因此，在第一个数字被分类后，它就处于正确的位置。然后，当您收到第三个数字时，将其正确地放在前一个数字之间。

当您收到更多数字时，这个过程会继续。关键在于，插入排序只能知道一些未来的数字来排序您已有的数字。它查看已排序的数字并将新数字按正确的顺序插入。这就是使插入排序成为“在线算法”的原因。

简单来说，这就像在收到所有卡片之前不需要看所有卡片的情况下整理您的卡片。这就是插入排序高效查找中位数元素的方法。

代码

输出

Median after taking 1 element is 2.0
Median after taking 2 elements is 3.0 
Median after taking 3 elements is 4.0 
Median after taking 4 elements is 5.0 
Median after taking 5 elements is 6.0

您共享的代码就像用一种名为 Python 的计算机语言编写的食谱。给定一个数字列表，它旨在执行一些数学运算并得到所谓的“运行中位数”，或者列表中的一种中间数字。

但是，食谱存在一些问题。设想一个食谱，其中某些成分已被移除或写错，说明的顺序不正确，最终会出现错误。我将以特定的方式分步提供正确的方法。

步骤 1：找到正确的位置

我们从一个名为“二分查找”的函数开始。此函数帮助我们在数字列表中定位特定数字的正确位置，以确保列表保持其顺序。这类似于在教育机构中为一本新出版物找到理想的书架。

步骤 2：计算运行中位数

现在，让我们谈谈食谱的主要部分，“median”函数。这部分负责查找列表中一组数字的运行中位数。

我们有一些特殊的杯子（变量），称为 i、j、posi、nums 和 c。

i 像一个指针，帮助我们跟踪我们在列表中的位置。

j 是另一个辅助指针。

posi 告诉我们要将新数字放在哪里。

nums 跟踪我们拥有的数字数量。

c 是我们的计数杯；它计算列表中有多少个数字。

我们首先打印单个数字（第一个数字）的中位数。

然后遍历列表，从第二个数字开始，到第一个数字结束。

我们使用“二分查找”方法确定每个整数在我们排序列表中的正确位置。在书架上，这类似于为一本新书选择理想的位置。

在将数字放置在正确位置之前，我们将测量杯（c）更改为反映我们现在在列表中多了一个数字。

我们接下来计算平均值，这相当于在列表中找到中间数字，作为我们下一步。如果数字的数量是偶数或奇数，我们会相应地处理。

最后，当满足一个特殊条件时（如果 name == "main"），我们的食谱就会运行。在上面的示例中，我们应用公式来获取整数范围 [2, 4, 6, 8, 9] 的连续中位数。

请记住，最初的菜肴存在一些错误，包括潦草的手写、不匹配的成分，甚至步骤的顺序不正确。我在上面的解释中修复了这些问题。确保遵循这个修正后的食谱才能正确运行。

示例 3

在处理二叉搜索树 (BST) 时，例如 AVL 或红黑树，我们通常希望找到中位数，即一组数字中的中间值。但我们如何有效地做到这一点呢？

一个巧妙的方法是为 BST 添加额外信息。节点本身会保留一个记录，其中包含以该节点位置为根的子树中存在的项目数量，而不仅仅是保存一个值。将此视为使每个节点成为一个小二叉树的主节点。第二个子节点具有大于根的组件，而左子节点具有小于根元素的组件。这样，根节点始终保存有效的中位数。

现在，这里有趣的地方来了。如果左子树和右子树具有相同数量的元素，则根节点包含这些子树中数据的平均值。但如果一个子树比另一个子树有更多的元素，根节点就会简单地采用较大子树根的数据。这使我们的树保持平衡，左子树和右子树最多相差一个元素。

传统的自平衡 BST 由于需要始终保持严格平衡而管理成本很高，而这对于查找中位数来说并非必需。我们不关心将数据完美排序；我们只想快速找到中位数。而这种增强的方法利用了巧妙的树结构来有效地跟踪中位数，而无需维护完美平衡树的不必要开销。

代码

输出

2
3.0
4
5.0
6

这个程序实现了一些非常有趣的事情。在一组数字中找到中间数字，就像变魔术一样。让我用通俗易懂的语言为您解释。

起初，脚本导入了一些独特的语言实用程序，有点像有用的工具。这些工具有助于排序和进行数学运算。

但是有一个名为“Median”的函数，它接受两个参数：一组数字和值的总数。

任务中有两个独特的堆，一个名为“min”，一个名为“max”。这些堆有助于跟踪较小和较大的数字。但不要与 Python 的“min”和“max”函数混淆；它们是不同的。

现在，想象您有一个数字列表。代码逐一遍历每个数字：

1. 它通过翻转数字的符号（正转负）并将其放入“min”堆中来执行一个小的技巧。这是因为 Python 的工具在“min”堆上工作得更好。
2. 然后，最小量从“min”堆转移到“max”堆。因此，数字的较小和较大的一半都保留在单独的堆中。
3. 如果“max”堆比“min”堆更大，则会将一个特定的数字从“max”堆转移到“min”堆以保持平衡。这确保了堆的大小几乎相等。
4. 最后，它会检查堆的大小是否相等。如果是，它会收集每个堆中的最高值，并将结果除以二以找出中间量（即中位数）。如果它们的大小不完全相等，它只会为您提供来自“min”堆的最大整数，它也是中位数。

在遍历完所有统计数据后，它会为您提供平均值。为了快速获取整数列表的平均值，上面的程序最终使用了一些巧妙的堆技巧。这就像魔法！

示例 4

代码

输出

2
3.0
4
5.0
6

这段 Python 代码定义了一个名为 RunningMedian 的类，该类使用两个堆：一个最大堆和一个最小堆来计算数字流的运行中位数。该程序展示了如何使用此类来确定任何整数流的当前运行中位数。

代码的语法解释如下：

导入 heapq 包：Python 包 heapq 提供堆队列技术。在此代码中，它用于实现最大堆和最小堆。

定义 RunningMedian 类。

使用 __init__ 方法初始化 min_heap 和 max_heap 池。通过在创建时取消整数，max_heap（一个最大堆）被实现为一个最小堆。

使用 insert 方法将另一个整数添加到数据结构中。后续操作如下：

如果 max_heap 为空，或者值小于或等于 max_heap 中的最大元素（已取反）的负值，则将负整数放入 max_heap。

否则，将值放入 min_heap。

然后，在插入每个元素后，该过程会确定 max_heap 的大小是否比 min_heap 的大小大一个以上。如果是，它会取消最大元素，将其从 max_heap 中弹出，然后将其推入 min_heap 以重新平衡堆。根据最后一个示例，如果 min_heap 大于 max_heap，则将最小元素从 min_heap 中删除，取反，然后推入 max_heap。

get_median 操作基于堆的最新配置计算并返回当前活动的平均值。

如果 max_heap（取反后）的最大元素与 min_heap 的最小元素相等，则标准差是第一个与第二个之比。

如果它们的尺寸不相等，平均值只是 max_heap 中的最高元素（取反后）。

创建一个包含以下输入的列表流：[2, 4, 6, 8, 9]。

创建 RunningMedian 类的多个新实例，名为 running_median。

反向遍历数字序列，边遍历边迭代。

使用 insert 方法将数字插入 running_median 对象。

通过调用 get_median 方法打印当前的运行中位数。

该代码基本上使用最大堆 (max_heap) 和最小堆 (min_heap) 来维护一个平衡的数字集，以便在逐个插入数字时有效地计算运行中位数。在流中的每次插入后，都会打印运行中位数。