Java中PriorityQueue构建大顶堆方法

2021-04-30 00:00:00 java 方法 构建

1.PriorityQueue概述

Java中PriorityQueue通过二叉小顶堆实现,可以用一棵完全二叉树表示。

有一种特殊的队列叫做PriorityQueue,即优先队列。优先队列的作用是能保证每次取出的元素都是队列中权值最小的(Java的优先队列每次取最小元素,及默认是小顶堆)。元素大小的评判可以通过元素本身的自然顺序,也可以通过构造时传入的比较器(如:Comparator)。

Java中PriorityQueue实现了Queue接口,不允许放入null元素;其通过堆实现,具体说是通过完全二叉树实现的小顶堆(任意一个非叶子节点的权值,都不大于其左右子节点的权值),也就意味着可以通过数组来作为PriorityQueue的底层实现。

2.PriorityQueue构建大顶堆

①.对于整数比较

PriorityQueue<Integer> queue = new PriorityQueue<Integer>(new Comparator<Integer>() {
            public int compare(Integer num1, Integer num2) {
                return num2 - num1;
            }
        });

②.new PriorityQueue(Comparator.reverseOrder());//直接用Comparator.reverseOrder()构建大顶堆

③.对于字符串拼接比较

Queue<String> queue = new PriorityQueue<>(new Comparator<String>() {
            @Override
            public int compare(String o1, String o2) {
                //字典序列大的放在堆顶
                return (o2 + o1).compareTo(o1 + o2);
            }
        });

    原文作者:JaxonChan
    原文地址: https://blog.csdn.net/JaxonChan/article/details/121193657
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系博主进行删除。

相关文章