PriorityQueue用法

一、基本概念

PriorityQueue（优先队列），在概念上，默认为小顶堆，元素单调递增排序。也可通过传入Comparator，重写其中的compare方法自定义排序规则；

在实现上，PriorityQueue实现了Queue接口，使用数组来存储数据，按照每层从左到右的顺序存放，因此它不允许存入null值。

二、常用方法总结

三、具体使用

1、实现降序排列（大顶堆）

方式一、lambda表达式

PriorityQueue<Integer> queue = new PriorityQueue<>(                (o1, o2) -> o2 - o1        );

方式二、重写compare方法

PriorityQueue<Integer> queue = new PriorityQueue<>(new Comparator<Integer>() {            @Override            public int compare(Integer o1, Integer o2) {                return o2 - o1;            }        });

2、实现自定义排序

示例一、按字符串的第三位进行降序排列

PriorityQueue<String> queue = new PriorityQueue<>(                (o1, o2) -> o2.charAt(2) - o1.charAt(2)        );

示例二、自定义一个类People，先按名字排序，再按年龄排序，再按身高排序

public class Solution {    public static void main(String[] args) {        PriorityQueue<People> queue = new PriorityQueue<>(                (o1, o2) -> {                    if (o1.getName().compareTo(o2.getName()) > 0) {                        return 1;                    } else if (o1.getName().compareTo(o2.getName()) < 0) {                        return -1;                    } else {                        if (o1.getAge() > o2.getAge()) {return 1;                        } else if (o1.getAge() < o2.getAge()) {return -1;                        } else {if (o1.getHeight() - o2.getHeight() > 0) {    return 1;} else if (o1.getHeight() - o2.getHeight() < 0) {    return -1;} else {    return 0;}                        }                    }                }        );        People one = new People("one", 12, 45.6f);        People two = new People("one", 12, 12.3f);        queue.add(one);        queue.add(two);        for (People tmp : queue) {            System.out.println(tmp);        }    }}class People {    private String name;    private int age;    private float height;    public People(String name, int age, float height) {        this.name = name;        this.age = age;        this.height = height;    }    public String getName() {        return name;    }    public void setName(String name) {        this.name = name;    }    public int getAge() {        return age;    }    public void setAge(int age) {        this.age = age;    }    public float getHeight() {        return height;    }    public void setHeight(float height) {        this.height = height;    }    @Override    public String toString() {        return "people{" +                "name='" + name + '\'' +                ", age=" + age +                ", height=" + height +                '}';    }}

3、解决TOP K问题

问题场景：从十亿个数中取最大/最小的100个数

解决方案：先取100个数构成小顶堆/大顶堆，后续每来一个数都与队头元素进行判断，比它小就直接丢弃，比它大就进队列中，直至访问完毕，最后剩下的即为所求答案。

来源地址：https://blog.csdn.net/weixin_43583736/article/details/127472973