performance - 在更改随机元素时保持排序

Question

我遇到了这个问题，我需要有效地删除列表/数组中的最小元素。这将是相当微不足道的解决 - 一个堆就足够了。

但是，现在的问题是，当我删除最小的元素时，会导致数据结构中其他元素的变化，这可能会导致顺序发生变化。一个例子是这样的：

我有一个元素数组：

[1,3,5,7,9,11,12,15,20,33]

当我从数组中删除“1”时，“5”和“12”分别更改为“4”和“17”。

[3,4,7,9,11,17,15,20,33]

因此不维持排序。

但是，被删除的元素将具有指向所有将被更改的元素的指针，但不知道将更改多少元素以及更改多少。

所以我的问题是：

从数据结构中删除最小元素同时保持排序时，存储这些元素以最大化性能的最佳方法是什么？还是我应该让它不分类？

我当前的实现只是将它们未排序的存储在一个向量中，因此时间复杂度为 O(N^2)，O(N) 用于查找最小元素，以及 N 个删除。

Answer 1

一种。

如果您有有序列表 L 的所有已更改元素的列表 M，

• 通过 M，并且对于每个元素

• 如果它仍然与 M 中的邻居一起订购，那就活下去吧。

• 如果它不符合邻居的顺序，则将其从 M 中排除。

• 此类排除的元素将创建一个列表 N

• 订单 N

• 使用一些算法来合并有序列表。http://en.wikipedia.org/wiki/Merge_algorithm

B.

如果您确定新元素很少且变化不大，只需使用冒泡排序即可。

Answer 2

我仍然会选择堆，由数组支持

如果每次弹出后只有少数元素发生变化，则在执行弹出操作后，对任何价值减少的项目执行 heapify up/down。它仍然是 O(nlog k) 值的顺序，其中 k 是数组的大小，n 是减小了大小的元素的数量。

如果很多项目的大小发生变化，那么您可以将其视为您有一个未排序的数组并且您只需从该数组创建一个堆的情况。