c – 如何快速地将元素重复插入到排序列表中

概述我没有正式的CS培训,所以请耐心等待. 我需要做一个模拟,可以抽象到以下(省略细节)： We have a list of real numbers representing the times of events. In each step, we remove the first event, and as a result of “processing” it, a few other ev 我没有正式的CS培训,所以请耐心等待.

我需要做一个模拟,可以抽象到以下(省略细节)：

We have a List of real numbers representing the times of events. In
each step,we

remove the first event,and as a result of “processing” it,a few other events may get inserted into the List at a strictly later time

and repeat this many times.

问题

我可以使用哪种数据结构/算法来尽可能高效地实现它？我需要显着增加列表中的事件/数字的数量.优先考虑的是尽可能快地列出长列表.

由于我在C中执行此 *** 作,STL或boost中已有哪些数据结构可以使实现它变得简单？

更多细节：

列表中的事件数是可变的,但保证在n和2 * n之间,其中n是一些模拟参数.当事件时间增加时,最新和最早事件的时间差也保证小于常数T.最后,我怀疑时间事件的密度虽然不是恒定的,但也有一个上下绑定(即所有事件永远不会强烈聚集在一个时间点附近)

到目前为止的努力：

正如问题的标题所说,我正在考虑使用排序的数字列表.如果我使用链表进行恒定时间插入,那么我很难找到以快速(次线性)方式插入新事件的位置.

现在我正在使用近似值,我将时间划分为桶,并跟踪每个桶中有多少事件.然后随着时间的推移逐个处理铲斗,当从前面移除一个铲斗时,总是在末端添加一个新铲斗,从而保持铲斗的数量不变.这很快,但只是近似值.

解决方法 最小堆可能适合您的需求.有一个 explanation here,我认为STL为您提供priority_queue.

插入时间为O(log N),删除为O(log N)

总结

以上是内存溢出为你收集整理的c – 如何快速地将元素重复插入到排序列表中全部内容，希望文章能够帮你解决c – 如何快速地将元素重复插入到排序列表中所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。