52

维基百科说：

选择算法：查找最小值、最大值、最小值和最大值、中值，甚至第 k 个最大元素都可以使用堆在线性时间内完成。

它所说的只是它可以完成，而不是如何完成。

你能给我一些关于如何使用堆来完成这件事的开始吗？

4

7 回答 7

21

您将使用 min-max-median 堆在恒定时间内找到最小值、最大值和中值（并花费线性时间来构建堆）。您可以使用顺序统计树来查找第 k 个最小/最大值。这两种数据结构都在这篇关于 min-max heaps [PDF] 的论文中进行了描述。最小最大堆是在最小堆和最大堆之间交替的二进制堆。

从论文中：

最小-最大-中值堆是具有以下属性的二叉树：

  1. 所有元素的中位数位于根

  2. 根的左子树是一个大小为上限[((n-1)/2)] 的最小-最大堆 Hl，其中包含小于或等于中位数的元素。右子树是一个大小为 floor[((n-1)/2)] 的最大最小堆 Hr，仅包含大于或等于中位数的元素。

该论文继续解释如何构建这样的堆。

在更彻底地阅读本文后，似乎构建 min-max-median 堆需要您首先找到中值（FTA：“使用任何一种已知的线性时间算法查找所有 n 个元素的中值”）。也就是说，一旦你建立了堆，你可以通过保持左侧的最小-最大堆和右侧的最大-最小堆之间的平衡来维持中值。DeleteMedian 将根替换为最大最小堆的最小值或最小最大堆的最大值（以保持平衡者为准）。

因此，如果您打算使用 min-max-median 堆来查找固定数据集的中值，那么您就是 SOL，但如果您在不断变化的数据集上使用它，这是可能的。

于 2010-04-09T23:34:46.310 回答
4

请参阅有关选择算法的此维基百科页面。特别是看 BFPRT 算法和 Median of Medians 算法。BFPRT 是概率线性的，并以快速排序为模型；中位数的中位数保证是线性的，但具有较大的常数因子，因此在实践中可能需要更长时间，具体取决于数据集的大小。

如果您只有几百或几千个元素可以从中选择中位数，我怀疑简单的快速排序和直接索引是最简单的。

于 2010-04-05T18:08:17.623 回答
4

那里可能有更好的算法，但我会这样做：

有两个桶和一个值。该值是中位数，两个桶分别是“大于中位数”和“小于中位数”。对于数组中的每个元素x，重新平衡桶，使得它们big_bucket的small_bucket大小相差不超过 1。当将项目从大桶移动到小桶时，它们首先必须通过中间值才能到达那里（即，差 2 将成功地将元素从一个桶推到下一个桶 - 差 1 将推动一个元素从一个桶到中值。）在您第一次通过数组结束时，该值应该是您的中值。

于 2010-04-05T18:08:44.487 回答
3

当最初的问题被问到时，也许它不在，但现在 wiki 有一个指向源的链接，这里是： http: //ftp.cs.purdue.edu/research/technical_reports/1991/TR%2091 -027.pdf

具体来说，请转到第 17 页，查看RSEL4的描述。他们在定理 3.2中证明了这个第 k 个选择算法的时间复杂度是 O(k)。所以你需要 O(n) 来构建堆，并且需要额外的 O(k) 来找到第 k 个最小的项目。

它并不像其他一些答案所建议的那样简单。

于 2012-02-15T00:36:56.720 回答
1

将第一个整数存储在数组中并将计数器设置为 1。然后循环遍历向量中的剩余整数。如果数组中的当前整数与存储的整数相同，则计数器加一，否则计数器减一。如果计数器达到零，则丢弃存储的整数并将其替换为数组中的当前整数。当您最终遍历所有整数时，您只剩下一个候选人。然后，您需要再次遍历数组并计算候选者的出现次数，以验证这确实是支配者。

static int FindDominator(int[] arr)
{
int counter = 1;
int candidate = arr[0];
for(int i = 1; i < n; i++)
{
   if(arr[i] == candidate) counter++
    else 
   {
        counter--;
        if(counter == 0) { candidate = arr[i]; counter = 1; }
    }
}
counter = 0;
for(int i = 0;  i < n; i++)
{
    if(arr[i] == candidate) counter++;
}
if(counter > n / 2) return candidate;
else return -1;
}
于 2015-03-26T17:34:17.980 回答
0

如果您对堆数据结构了解更多，您将很容易理解事实就是如此。堆结构可以在 O(n) 时间内构建，有最小堆和最大堆。min heap root element 会给你最小的元素。最大堆根元素将为您提供最大元素。只需构建堆，您就可以找到最小值和最大值。中位数和第 k 大的想法相同，在构建堆时，您可以通过查看树的左分支或右分支并保持恒定的内存量来存储元素编号来找到中位数和第 k 大。等等

于 2010-04-08T03:32:37.313 回答
-1

显然，O(n) 中的 min 和 max 很简单，不需要堆。

K'th 最大的可以相当简单地通过维护到目前为止前 k 个值的 k 大小堆来完成。运行时间为 O(n*logk)。如果 k 是固定大小且 k << n，则可以调用该线性时间。

我不认为中位数是可能的。仅仅创建一个 O(n) 大小的堆需要 O(n*logn) 时间。

编辑： 好的，在考虑了更多之后，IVlad 是对的。您可以在 O(n) 中创建一个固定大小的堆。但是......这对他的中位数问题没有帮助。线性堆创建技术仅生成一个有效堆作为其最终输出。进行 n 次插入的简单方法，在每一步之后产生一个有效的堆是 O(n*logn)。

在我看来，使用堆来查找中位数需要使用那些正在运行的子堆。例如，这里发布了一个答案（现在似乎已被删除），该答案链接到一篇建议解决此问题的算法的博客文章。它使用两个堆（较小的一半和较大的一半）跟踪运行中位数，因为它只通过数据一次。这将需要更慢、更简单的堆方法，因为它依赖于在插入和删除有效堆时维护有效堆。

有没有其他方法可以使用线性一次性堆创建技术找到中值？

于 2010-04-05T18:12:15.530 回答