algorithm - 查找最大和 n/3 最大元素的实现

Question

假设你总是得到数字，而你不知道一开始会有多少个数字。在任何时候我都希望能够立即输出最大的数字和 n/3 最大的数字(其中 n 是到目前为止输入的数字的数量)(在 O(1) 中)。输入新数字的最长时间为 O(log(n))。

实现它的最佳方法是什么？

Answer 1

你可以用两个 heaps 来实现它: 一个最小堆 (A) 和一个最大堆 (B)。

想法是将 n/3 个最大值存储在 A 中，将其余值存储在 B 中，这样 B 中的最大值就是 n/3 个最大值(从零开始计数)。假设 n/3 被截断以防 n 不是三的倍数，并且结果值是从零开始的 (n/3 == 0 表示最大值也是 n/3 最大的元素)，这意味着必须保持以下不变性:

A.size == floor((A.size + B.size)/3)

...归结为:

0 <= B.size - 2*A.size < 3 

上述条件可能会有所不同，具体取决于对 n/3 元素的解释(它是基于 0 的、基于 1 的、舍入的、截断的……)，以及一些当总集合中的元素少于 3 个时，可能需要特别注意，具体取决于该定义。

要添加一个值v，您首先要确定它属于哪个堆。如果它小于当前 n/3^th 最大值——B 中的最大值——那么它属于 B，否则属于 A。不变性可能会被破坏，必须通过从任一堆中提取一个值并将其添加到另一个堆来恢复。

更正式的 v 添加如下:

if v < B.peek():
    B.add(v)
    if B.size - 2*A.size >= 3:
        A.add(B.pull())
else:
    A.add(v)
    if B.size - 2*A.size < 0:
        B.add(A.pull())

获得n/3^th 最大值的实现是:

B.peek()

以上所用方法的时间复杂度为:

• 大小:O(1)
• 偷看:O(1)
• 拉:O(logn)
• 添加:O(logn)

保持整体最大值是一项容易的任务。堆仅用于跟踪 n/3^th 最大值。