循环创建双精度并将它们插入到排序数组中,在C中

Question

假设我有一组已排序的双打.

{ 0.124, 4.567, 12.3 }

一个正的,非零的double是由代码的另一部分创建的,需要在保持排序的同时插入到该集合中.例如,如果创建的double是7.56,则最终结果是,

{ 0.124, 4.567, 7.56, 12.3 }

在我的代码中,这个"创建双重并插入有序集合"过程然后重复了很多次.可能是500k到100万次.我不知道总共会创造多少双打,但我知道上限.

尝试

我天真的第一种方法是创建一个长度=上限的数组,并用零填充它,然后添加初始的双精度集("add"=用双精度替换0值的数据).每当创建一个double时,我将它添加到数组并执行插入排序,我读到这对排序有序数组很有用.

题

我有一种感觉,运行500k到100万插槽将是一个严重的性能问题.(或者我错了？)在C中是否有更高效的数据结构和/或算法？

编辑:

我想保持集合排序的原因是因为在每次"创建双重并插入有序集合"过程之后,我需要能够查找该集合中的最小元素(并且可能通过将其替换为0来删除它) ).我认为最好的方法是保持集合排序.

但如果情况不是这样,也许还有另一种选择吗？

Answer 1

由于您要做的只是在每次迭代中拉出最小元素,而是使用最小堆.您可以实现它们以进行O(1)插入,O(1)find-min和O(1)减少键操作(但请注意,删除最小元素总是需要O(log n)时间).对于你正在做的事情,堆将大大加快.