如何不断地从两个不同的列表中找到两个最小值？

Question

我有两个包含整数的不同列表，我需要不断地找到这两个列表之间的两个最小值；我应该注意，我不想将这两个列表合并在一起，因为它们是不同的类型。

我想知道我的方法是好是坏。如果不好，请让我知道如何提高效率。

始终按降序对两个列表进行排序，因此分钟将排在底部
从 list1 中找到两分钟并将其与 list2 中的两分钟进行比较，然后从这四个值中找到两分钟
从关联列表中删除两个分钟，将它们的值组合在一起（必需）并将其添加到列表 2

我实际上是在执行 Huffman 代码的一部分，我想在其中按降序排列字符的频率列表。

Answer 1

在 List 中找到最小值可以在线性时间内完成，无需任何排序。每次排序和查找最小值将是 O(m*nlgn) m 是迭代次数，n 是列表的大小）。

更好的方法是使用 PriorityQueue（最小堆），其中最小值始终位于堆的顶部，而不是在每次迭代时都进行排序。

通常使用 min-heap 实现 Huffman codes 和贪心算法。

Answer 2

虽然这肯定有效，但始终保持列表排序的任务应该引起关注：

如果您的列表允许随机访问（即 ArrayLists），那么从中删除的过程将花费您 O(n)
如果你的列表允许 O(1) 次删除（即 LinkedLists），那么找到插入点的过程就是 O(n)

这是在初始排序之上，这将花费您 O(n*log₂n)。换句话说，首先对列表进行排序没有任何优势：维护它们每次操作的成本为 O(n)，因此您还不如进行线性搜索。

换句话说，该算法有效，但效率低下。不要维护排序列表，而是使用为您维护最小值或最大值的容器，并允许快速 insertions/deletions（例如 PriorityQueue）。

Answer 3

为什么不将最小值保存在变量中而不是保存排序列表？

List<Integer> list1, list2;
int min1 = Integer.MAX_VALUE, min2 = Integer.MAX_VALUE;

void setMin(int newValue) {
    if (newValue < min1) {
        min1 = newValue;
    } else if (newValue < min2) {
        min2 = newValue;
    }
}

void updateList1(int newValue) {
    setMin(newValue);
    list1.add(newValue);
}

void updateList2(int newValue) {
    setMin(newValue);
    list2.add(newValue);
}

如何不断地从两个不同的列表中找到两个最小值？

How to constantly find the two smallest values from two different lists?

java

list

min

huffman-code