使用ArrayList的优先级队列的java性能

Question

我目前正在研究一个最小优先级队列，它在添加项目时保持自身的排序。建议的实现将新项添加到已排序的ArrayList的末尾，然后在列表中查找这些项的正确位置。因此，它会与列表中的每个前一个元素交换，直到添加的项按顺序排列

在这个方法被提出之前，我使用的实现涉及通过排序列表进行比较，标记要插入项的索引，然后使用Java的add（int index，Object O）方法，而不是仅仅添加到末尾

我试图理解这两种方法之间的性能差异。我知道如果我插入，所有的尾部索引都必须被更正（这由类方法负责）。但这真的比在列表中切换回来效率低吗

提前感谢您的解释

Answer 1

如上所述，这两个选项都将在O（n）时间内运行（我认为）。然而，第二个选项（即您的初始实现）可能会有更好的恒定因子，因为一次移动一组元素可能（而且可能会）比一次移动一个元素更有效，尤其是在必须移动大量元素的情况下。所以我想说，您最初的实现效率更高，除非您的最终插入点几乎总是接近数组的末尾，此时System.arraycopy()的开销可能会支配实际工作所需的时间，但不会太多

我想你可以把这两种情况看作是对bubblesort（建议的实现）和插入排序（初始实现）的一次迭代的近似比较。两者的时间复杂度相同，但插入排序的单个迭代几乎总是（或者可能总是？）由于操作更少，运行速度更快

以此为例（为简单起见，假设可调整大小的数组）：

int[] a = new int[] {1, 2, 4, 5};

然后说你想插入3

您最初的实现是这样的：

1. 查找要插入的索引。3个比较以找到index == 2
2. 指数处的移位元素>；2.2操作：5班在一个地方，4班在一个地方。（这可能是一个操作，取决于System.arraycopy()的实现方式）。结果是{1, 2, 0, 4, 5}
3. 插入元素。1.手术。最终结果是{1, 2, 3, 4, 5}

总计：3次比较，3次操作

您的新实现将如下所示：

1. 在末尾插入元素。1.手术。结果是{1, 2, 4, 5, 3}
2. 比较看是否需要交换。1.比较。需要交换
3. 交换。3个操作：将5分配给临时变量，将3分配给索引3，将临时变量分配给索引4。结果是{1, 2, 4, 3, 5}
4. 比较看是否需要交换。1.比较。需要交换
5. 交换。3个操作：将4分配给临时变量，将3分配给索引2，将临时变量分配给索引3。结果是{1, 2, 3, 4, 5}
6. 比较看是否需要交换。1.比较。不需要交换。完成了

总计：3次比较，7次操作

作为补充说明，您可能最好使用二进制搜索来查找插入点，而不是直接的线性搜索