c – 在文件输入期间跟踪最高5个数字

发布时间：2020-12-16 10:00:03 所属栏目：百科来源：网络整理

导读：所以我要说我有一个结构 struct largestOwners{ string name; double amountOwned;}; 我正在使用带有300个名称和金额的ifstream从文件中读取它. 如何在输入过程中跟踪最高的5个数字？所以我不必排序,而是在ifstream输入期间跟踪它. 我的目标是在输入过程中跟

所以我要说我有一个结构

struct largestOwners
{
    string name;
    double amountOwned;
};

我正在使用带有300个名称和金额的ifstream从文件中读取它.

如何在输入过程中跟踪最高的5个数字？所以我不必排序,而是在ifstream输入期间跟踪它.

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

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

让我们说,当我阅读它时,文本文件看起来像这样.

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

谢谢！

解决方法

要跟踪传入数字流中最高的5个数字,可以使用大小为5的 min-heap(C STL设置可以用作最小堆).

首先使用前5个数字填充min-heap.之后,对于每个传入元素,将其与最大的5个数字(最小堆的根)中的最小值进行比较.如果当前数字小于该值,则不执行任何操作,否则删除第5个最大值(从最小堆弹出)并将当前数字插入最小堆.

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

例如,请考虑以下数字流：

1 2 5 6 3 4 0 10 3

最小堆最初将具有1 2 3 5 6.

遇到4时,1被删除,4被插入.
Min heap现在看起来像这样：2 3 4 5 6

遇到0时,没有任何反应.

在遇到10时,2被删除,10被插入.
Min heap现在看起来像这样：3 4 5 6 10

遇到3时,没有任何反应.

所以最后一组5个最大的元素都包含在堆中(3 4 5 6 10)

你甚至可以调整它来跟踪输入数字流中的k个最高元素.只需将最小堆的大小更改为k即可.

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!