c++ - 在文件输入过程中跟踪最高的 5 个数字

Question

假设我有一个结构

struct largestOwners
{
    string name;
    double amountOwned;
};

我正在使用带有 300 个名称和数量的 ifstream 从文件中读取它。

我怎样才能在输入过程中跟踪最大的 5 个数字？所以我不必在之后进行排序，而是在 ifstream 输入期间跟踪它。

我的目标是在输入过程中跟踪 5 个最高金额，以便稍后轻松打印出来。并节省时间/处理而不是在将来做

我知道我可以将它存储在一个数组或另一个结构中，但是在结构的 ifstream 输入期间跟踪它的好算法是什么？

假设文本文件看起来像这样，当我读入它时。

4025025 Tony
66636 John
25 Tom
23693296 Brady
363 Bradley
6200 Tim

谢谢!

Answer 1

要跟踪传入号码流中最高的 5 个号码，您可以使用 min-heap大小为 5(C++ STL set 可用作最小堆)。

首先用前 5 个数字填充最小堆。之后，对于每个传入元素，将其与您拥有的最大 5 个数字中的最小数字(最小堆的根)进行比较。如果当前数字小于该数字，则什么都不做，否则移除第 5 个最大的数字(从最小堆中弹出)并将当前数字插入到最小堆中。

在最小堆中删除和插入将花费 O(log n) 时间。

例如，考虑以下数字流:

1 2 5 6 3 4 0 10 3

最小堆最初将有 1 2 3 5 6。

在遇到 4 时，删除 1 并插入 4。最小堆现在看起来像这样:2 3 4 5 6

在遇到 0 时，没有任何反应。

在遇到 10 时，删除 2 并插入 10。最小堆现在看起来像这样:3 4 5 6 10

在遇到 3 时，没有任何反应。

因此，您的最后一组 5 个最大元素包含在堆中 (3 4 5 6 10)

您甚至可以调整它以跟踪传入数字流中的 k 个最高元素。只需将最小堆的大小更改为 k。