优先级队列

命运对每个人都是一样的,不一样的是各自的努力和付出不同,付出的越多,努力的越多,得到的回报也越多,在你累的时候请看一下身边比你成功却还比你更努力的人,这样,你就会更有动力。

导读:本篇文章讲解 优先级队列,希望对大家有帮助,欢迎收藏,转发!站点地址:www.bmabk.com,来源:原文

优先级队列

优先级队列是一种先进先出的数据结构,操作的数据带有优先级,这种数据结构就是优先级队列(PriorityQueue),优先级队列是一种先进先出(FIFO)的数据结构,与队列不同的是,操作的数据带有优先级,通俗的讲就是可以比较大小,在出队列的时候往往需要优先级最高或者最低的元素先出队列,这种数据结构就是优先级队列(PriorityQueue)。

不能插入null对象,否则会抛NullPointerException异常

PriorityQueue底层使用堆数据结构

PriorityQueue默认是小堆,如果想要创建大堆可以使用比较器

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

o2-o1是创建大堆,o1-o2是创建小堆

JDK1.8中PriorityQueue底层采用了堆数据结构,堆其实就是对完全二叉树的元素作出了一些调整

所谓堆就是将一组数据按照完全二叉树的顺序存储方式存储,保证每一个根结点元素大于它的孩子结点的元素(大根堆)或者小于它的孩子结点的元素(小根堆),堆中某个结点的值总是不大于或着不小于其父节点的值。堆是一颗完全二叉树。

比较器

Comparable和Comparator都是两个接口,接口都可以用来实现集合中元素的比较、排序,Comparator位于包java.util下,而Comparable位于包java.lang下,Comparable接口将比较代码嵌入自身类中,而Comparator既可以嵌入到自身类中,也可以在一个独立的类中实现比较。

Integer、String等这些基本类型的JAVA封装类都已经实现了Comparable接口,这些类对象本身就支持自比较,直接调用Collections.sort()就可以对集合中元素的排序,无需自己去实现Comparable接口。而有些自定义类的List序列,当这个对象不支持自比较或者自比较函数不能满足你的要求时,你可以写一个比较器来完成两个对象之间大小的比较,也就是指定使用Comparator(临时规则排序,也称作专门规则排序),如果不指定Comparator,那么就用自然规则排序,这里的自然顺序就是实现Comparable接口设定的排序方式。

Top-k问题

求前k个最大,建小堆

求前k个最小,建大堆

代码示例

给你一个整数数组 nums 和一个整数 k ,请你返回其中出现频率前 k 高的元素。你可以按
任意顺序 返回答案。

输入: nums = [1,1,1,2,2,3], k = 2

输出: [1,2]

 public int[] topKFrequent(int[] nums, int k) {
        Map<Integer,Integer> map=new HashMap<>();
        for (int num : nums) {
            int orDefault = (int) map.getOrDefault(num, 0);
            map.put(num,orDefault+1);
        }
//        PriorityQueue<Map.Entry<Integer, Integer>> queue=new PriorityQueue<>(new Comparator<Map.Entry<Integer, Integer>>() {
//            @Override
//            public int compare(Map.Entry<Integer, Integer> o1, Map.Entry<Integer, Integer> o2) {
//                return o1.getValue()-o2.getValue();
//            }
//        });
        PriorityQueue<Map.Entry<Integer, Integer>> queue=new PriorityQueue<>((o1, o2) -> o1.getValue()-o2.getValue());

        for (Map.Entry<Integer, Integer> integerIntegerEntry : map.entrySet()) {
            queue.add(integerIntegerEntry);
            if(queue.size()>k)
                queue.poll();
        }
        System.out.println(queue);
        int[] dp=new int[k];
        for(int i=k-1;i>=0;i--){
            dp[i]=queue.poll().getKey();
        }
        return dp;

    }
Comparable可以认为是一个内比较器,实现了Comparable接口的类有一个特点,就是这些类是可以和自己比较的,至于具体和另一个实现了Comparable接口的类如何比较,则依赖compareTo方法的实现

public class Person implements Comparable<Person>{
    private String username;
    private Integer age;
  
 
    @Override
    public int compareTo(Person o) {
        return this.age-o.age;
    }
}

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

文章由半码博客整理,本文链接:https://www.bmabk.com/index.php/post/143056.html

(0)
飞熊的头像飞熊bm

相关推荐

发表回复

登录后才能评论
半码博客——专业性很强的中文编程技术网站,欢迎收藏到浏览器,订阅我们!