小根堆和大根堆，在使用Stream流时顺序错误

出现场景

题目描述

明明生成了N 个1到500之间的随机整数。请你删去其中重复的数字，即相同的数字只保留一个，把其余相同的数去掉，然后再把这些数从小到大排序，按照排好的顺序输出。

数据范围： 1≤ n ≤1000 1≤ n ≤1000 ，输入的数字大小满足 1 ≤val≤ 500 1 ≤val≤ 500

出现问题解法

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        PriorityQueue<Integer> queue = new PriorityQueue<Integer>(n);
        while (in.hasNextInt()) { // 注意 while 处理多个 case
            int a = in.nextInt();
            if(!queue.contains(a)){queue.offer(a);}
        }
        queue.stream().forEach(e -> {
            System.out.println(e);
        });
    }
}

当时想着流式遍历输出提高性能，但是提交代码一个用例都没有通过

立马反应过来是流式输出的锅，直接改成普通的poll一个一个输出就可以通过，这是因为小根堆的定义是：

根节点小于子节点（但是不能保证整棵树的有序性）

所以我们直接全部遍历是错误的顺序，因为每次的插入和删除都会触发一个siftUp方法来进行树结构的调整。

借这个机会复习一下小根堆

一，堆的插入

从末尾节点的父节点的这棵树开始调整，根据小根堆的性质，越小的数据往上移动，注意，被调整的节点还有子节点的情况，需要递归进行调整。

例子：11,25,3,8,5,9,17,28,94,120,我们模拟 5 插入的场景,优先被插入到树的底部

接下来进行递归调整

向上和根节点进行比较，如果比他小就进行交换

继续递归，知道不需要交换结束

发现不需要交换后，这次插入就结束。所以最后的数组顺序为：

二，堆的删除

对于最大堆和最小堆，删除操作是针对堆顶元素而言的，即把末尾元素移动到堆顶，再自定向下(重复构建堆的操作)，递归调整。

在这里插入图片描述

总结

内存占用：二叉排序树占用的内存空间比我们存储的数据要多，需要分配额外的内存来存储指针指向其左右子节点。堆的实现结构是数据，根据数组具有下标这一特性来执行左/右子节点。
节点的顺序：在二叉排序树中，左子节点必须比父节点小，右子节点必须比父节点大。但是在堆中并非如痴，在小根堆中两个子节点都必须比父节点小，并且左右子节点的数据大小是不确定的。
搜索性能：二叉排序树是为了实现动态查找而涉及的数据结构，它是面向查找操作的，在二叉排序树中查找一个节点的平均时间复杂度是O(logn)；在堆中搜索并不是第一优先级，堆是为了实现排序而实现的一种数据结构，它不是面向查找操作的，因为在堆中查找一个节点需要进行遍历，其平均时间复杂度是O(n)。