使用 Java 流构建二叉树。是否可以在 Java 流排序同时减少？

Question

我想使用 Java 流从输入字符串构建一个 Huffman tree。

我现在就是这样做的。

Class MyNode 和所有需要的构造函数：

public static class MyNode {
    Character value;
    MyNode left;
    MyNode right;
    long freq;
    ...
}

读取一行并获取 MyNodes 列表：

Scanner scan = new Scanner(System.in);
String input = scan.next();
List<MyNode> listOfNodes = input.chars().boxed()
            .collect(Collectors.groupingBy(Function.identity(), Collectors.counting())) 
            .entrySet()
            .stream().sorted(Comparator.comparingLong(Map.Entry::getValue))
            .map(x -> new MyNode((char)x.getKey().intValue(), x.getValue()))
            .collect(Collectors.toList());

这个 while 循环我想用 Stream 中的内容替换：

while (listOfNodes.size() > 1) {
        MyNode first = listOfNodes.get(0);
        MyNode second = listOfNodes.get(1);
        listOfNodes.remove(first);
        listOfNodes.remove(second);
        listOfNodes.add(new MyNode(first.freq + second.freq, first, second));
        listOfNodes.sort(Comparator.comparingLong(MyNode::getFreq));
    }

在 while 循环中，我像这样构建树

第一个想法是使用 Stream reduce，但后来我需要在每次 reduce 后对结果列表进行排序。

Answer 1

这不是一项可以从使用流中获益的任务 API。尽管如此，仍有改进的方法。

为了插入单个元素而对整个列表进行排序，承担了不必要的开销。由于列表是排序的，您可以使用二进制搜索来有效地找到正确的插入位置，以便列表保持排序：

while(listOfNodes.size() > 1) {
    MyNode first = listOfNodes.remove(0), second = listOfNodes.remove(0);
    MyNode newNode = new MyNode(first.freq + second.freq, first, second);
    int pos = Collections.binarySearch(listOfNodes, newNode,
                                       Comparator.comparingLong(MyNode::getFreq));
    listOfNodes.add(pos<0? -pos-1: pos, newNode);
}

请注意，您可以通过颠倒顺序来提高此代码的效率，以便从列表末尾删除（实际上是 ArrayList）。

但更好的选择是使用排序后的数据结构，例如

PriorityQueue<MyNode> queueOfNodes = input.chars().boxed()
    .collect(Collectors.groupingBy(Function.identity(), Collectors.counting())) 
    .entrySet().stream()
    .map(x -> new MyNode((char)x.getKey().intValue(), x.getValue()))
    .collect(Collectors.toCollection(
        () -> new PriorityQueue<>(Comparator.comparingLong(MyNode::getFreq))));

MyNode result = queueOfNodes.remove();
while(!queueOfNodes.isEmpty()) {
    MyNode second = queueOfNodes.remove();
    queueOfNodes.add(new MyNode(result.freq + second.freq, result, second));
    result = queueOfNodes.remove();
}

使用 Java 流构建二叉树。是否可以在 Java 流排序同时减少？

Building binary tree using Java Stream. Is it possible in Java Stream sorting while reduce?

sorting

reduce

java-8

java-stream