Java之PriorityQueue的用法

目录

PriorityQueue用法

一、基本概念

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

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

二、常用方法总结

方法作用add();队尾插入元素，调整堆结构，失败时抛异常offer();队尾插入元素，调整堆结构，失败时抛falseremove();根据value值删除指定元素，调整堆结构，失败时抛异常poll();删除队头元素，调整堆结构，失败时抛nullelement();获取队列头元素peek();获取队列头元素clear();清空队列size();获取队列元素个数contains();判断队列中是否包含指定元素isEmpty();判断队列是否为空

三、具体使用

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

方式一、lambda表达式

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

方式二、重写compare方法

PriorityQueue<Integer> queue =newPriorityQueue<>(newComparator<Integer>(){@Overridepublicintcompare(Integer o1,Integer o2){return o2 - o1;}});

2、实现自定义排序

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

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

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

publicclassSolution{publicstaticvoidmain(String[] args){PriorityQueue<People> queue =newPriorityQueue<>((o1, o2)->{if(o1.getName().compareTo(o2.getName())>0){return1;}elseif(o1.getName().compareTo(o2.getName())<0){return-1;}else{if(o1.getAge()> o2.getAge()){return1;}elseif(o1.getAge()< o2.getAge()){return-1;}else{if(o1.getHeight()- o2.getHeight()>0){return1;}elseif(o1.getHeight()- o2.getHeight()<0){return-1;}else{return0;}}}});People one =newPeople("one",12,45.6f);People two =newPeople("one",12,12.3f);
        queue.add(one);
        queue.add(two);for(People tmp : queue){System.out.println(tmp);}}}classPeople{privateString name;privateint age;privatefloat height;publicPeople(String name,int age,float height){this.name = name;this.age = age;this.height = height;}publicStringgetName(){return name;}publicvoidsetName(String name){this.name = name;}publicintgetAge(){return age;}publicvoidsetAge(int age){this.age = age;}publicfloatgetHeight(){return height;}publicvoidsetHeight(float height){this.height = height;}@OverridepublicStringtoString(){return"people{"+"name='"+ name +'\''+", age="+ age +", height="+ height +'}';}}

3、解决TOP K问题

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

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