c - 在 C 中创建 double 并将它们插入排序数组的循环

Question

假设我有一组已排序的 double 。

{ 0.124, 4.567, 12.3 }

一个正的、非零的 double 由代码的另一部分创建，需要插入到这个集合中，同时保持它排序。比如创建的double是7.56，最后的结果是，

{ 0.124, 4.567, 7.56, 12.3 }

在我的代码中，这个“创建 double 并插入排序集中”的过程会重复很多次。可能是 50 万到 100 万次。我不知道总共会创建多少个 double ，但我知道上限。

尝试

我天真的第一种方法是创建一个长度为上限的数组，并用零填充它，然后向其中添加初始的 double 集(“添加”= 用 double 值替换 0 值条目)。每当创建 double 时，我都会将其添加到数组中并执行插入排序，我读到这对于排序有序数组很有用。

问题

我感觉运行 50 万到 100 万个插入槽将是一个严重的性能问题。 (或者我错了吗？)在 C 中是否有更有效的数据结构和/或算法来执行此操作？

编辑:

我想保持集合排序的原因是因为在每次“创建 double 并插入排序集合”过程之后，我需要能够查找该集合中的最小元素(并可能通过替换它来删除它带有 0)。我认为最好的方法是保持集合有序。

但如果不是这种情况，也许还有其他选择？

Answer 1

由于您只想在每次迭代中取出最小元素，因此请使用 min-heap反而。您可以将它们实现为具有 O(1) 插入、O(1) 查找最小 和 O(1) 减少键 操作(尽管请注意，删除最小元素总是需要 O(log n) 时间)。对于您正在做的事情，堆会快得多。