Java PriorityQueue - Java教程

由网友 大卫 发布 阅读 11

Java PriorityQueue - Java教程

在本教程中,我们将借助示例学习Java集合框架的PriorityQueue类。

PriorityQueue类提供堆数据结构的功能。

它实现了Queue接口

Java PriorityQueue类实现Queue接口。

与普通队列不同,优先队列元素是按排序顺序检索的。

假设我们想以升序检索元素。在这种情况下,优先队列的头是最小的元素。检索到该元素后,下一个最小的元素将成为队列的头。

需要注意的是,优先队列的元素可能没有排序。但是,元素总是按排序顺序检索的。

创建PriorityQueue

为了创建优先级队列,我们必须导入java.util.PriorityQueue包。导入程序包后,可以使用以下方法在Java中创建优先级队列。

PriorityQueue<Integer> numbers = new PriorityQueue<>();

这里,我们创建了一个没有任何参数的优先级队列。在这种情况下,优先级队列的头是队列中最小的元素。元素将按升序从队列中移除。

但是,我们可以借助 Comparator 接口自定义元素的顺序。我们将在本教程的后面部分中对此进行了解。

PriorityQueue方法

PriorityQueue类提供了Queue接口中存在的所有方法的实现。

将元素插入PriorityQueue

  • add() - 将指定的元素插入队列。如果队列已满,则会引发异常。

  • offer() - 将指定的元素插入队列。如果队列已满,则返回false。

例如,

import java.util.PriorityQueue;

class Main {
    public static void main(String[] args) {

        //创建优先队列
        PriorityQueue<Integer> numbers = new PriorityQueue<>();

        //使用add()方法
        numbers.add(4);
        numbers.add(2);
        System.out.println("PriorityQueue: " + numbers);

        //使用offer()方法
        numbers.offer(1);
        System.out.println("更新后的PriorityQueue: " + numbers);
    }
}

输出结果

PriorityQueue: [2, 4]
更新后的PriorityQueue: [1, 4, 2]

在这里,我们创建了一个名为的优先级队列numbers。我们已将4和2插入队列。

虽然4被插入到2之前,但队列的头是2。这是因为优先级队列的头是队列中最小的元素。

然后,我们将1插入队列。 现在重新排列了队列,以将最小的元素1存储到队列的开头。

访问PriorityQueue元素

要从优先级队列访问元素,我们可以使用peek()方法。此方法返回队列的头部。例如,

import java.util.PriorityQueue;

class Main {
    public static void main(String[] args) {

        // 创建优先级队列
        PriorityQueue<Integer> numbers = new PriorityQueue<>();
        numbers.add(4);
        numbers.add(2);
        numbers.add(1);
        System.out.println("PriorityQueue: " + numbers);

        //使用 peek() 方法
        int number = numbers.peek();
        System.out.println("访问元素: " + number);
    }
}

输出结果

PriorityQueue: [1, 4, 2]
访问元素: 1

删除PriorityQueue元素

  • remove() - 从队列中删除指定的元素

  • poll() - 返回并删除队列的开头

例如,

import java.util.PriorityQueue;

class Main {
    public static void main(String[] args) {

        // 创建优先队列
        PriorityQueue<Integer> numbers = new PriorityQueue<>();
        numbers.add(4);
        numbers.add(2);
        numbers.add(1);
        System.out.println("PriorityQueue: " + numbers);

        //使用remove()方法
        boolean result = numbers.remove(2);
        System.out.println("元素2是否已删除? " + result);

        //使用poll()方法
        int number = numbers.poll();
        System.out.println("使用poll()删除的元素: " + number);
    }
}

输出结果

PriorityQueue: [1, 4, 2]
元素2是否已删除? true
使用poll()删除的元素: 1

遍历PriorityQueue

要遍历优先级队列的元素,我们可以使用iterator()方法。为了使用此方法,我们必须导入java.util.Iterator包。例如,

import java.util.PriorityQueue;
import java.util.Iterator;

class Main {
    public static void main(String[] args) {

        //创建优先级队列
        PriorityQueue<Integer> numbers = new PriorityQueue<>();
        numbers.add(4);
        numbers.add(2);
        numbers.add(1);
        System.out.print("使用iterator()遍历PriorityQueue : ");

        //使用iterator()方法
        Iterator<Integer> iterate = numbers.iterator();
        while(iterate.hasNext()) {
            System.out.print(iterate.next());
            System.out.print(", ");
        }
    }
}

输出结果

使用iterator()遍历PriorityQueue : 1, 4, 2,

PriorityQueue其他方法

方法内容描述
contains(element)在优先级队列中搜索指定的元素。如果找到该元素,则返回true,否则返回false。
size()返回优先级队列的长度。
toArray()将优先级队列转换为数组,并返回它。

PriorityQueue 比较器(comparator)

在以上所有示例中,优先级队列元素都是按自然顺序(升序)检索的。 但是,我们可以自定义此顺序。

为此,我们需要创建自己的comparator类,它实现了Comparator接口。例如

import java.util.PriorityQueue;
import java.util.Comparator;
class Main {
    public static void main(String[] args) {

        //创建优先级队列
        PriorityQueue<Integer> numbers = new PriorityQueue<>(new CustomComparator());
        numbers.add(4);
        numbers.add(2);
        numbers.add(1);
        numbers.add(3);
        System.out.print("PriorityQueue: " + numbers);
    }
}

class CustomComparator implements Comparator<Integer> {

    @Override
    public int compare(Integer number1, Integer number2) {
        int value =  number1.compareTo(number2);
        //元素以相反的顺序排序
        if (value > 0) {
            return -1;
        }
        else if (value < 0) {
            return 1;
        }
        else {
            return 0;
        }
    }
}

输出结果

PriorityQueue: [4, 3, 1, 2]

在上面的示例中,我们创建了一个优先级队列,将CustomComparator类作为参数传递。

CustomComparator类实现了Comparator接口。

然后,我们重写compare()方法。该方法现在使元素的头成为最大的数。

Java LinkedList(链表) Java Queue 接口