Java优先级队列：实现大堆

作者：暴富2021

2024.02.17 03:03

浏览量：5

简介：在Java中，优先级队列默认实现是小顶堆，但可以通过自定义比较器实现大顶堆。下面是一个简单的示例，演示如何使用Java的PriorityQueue实现大顶堆。

Java中的PriorityQueue默认实现是小顶堆，即最小的元素总是位于队列的头部。但是，我们可以通过自定义比较器来实现大顶堆，即最大的元素总是位于队列的头部。

要实现大顶堆，我们需要创建一个自定义比较器，并将其传递给PriorityQueue的构造函数。比较器必须实现Comparator接口，并重写compare()方法。在compare()方法中，我们将比较两个元素，如果第一个元素大于第二个元素，则返回正数；如果两个元素相等，则返回0；如果第一个元素小于第二个元素，则返回负数。

下面是一个示例代码，演示如何使用Java的PriorityQueue实现大顶堆：

import java.util.Comparator;
import java.util.PriorityQueue;
public class MaxHeapPriorityQueue {
    public static void main(String[] args) {
        // 创建自定义比较器
        Comparator<Integer> maxHeapComparator = new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2 - o1; // 大顶堆比较器
            }
        };
        // 创建大顶堆优先级队列
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(maxHeapComparator);
        // 向队列中添加元素
        maxHeap.add(3);
        maxHeap.add(5);
        maxHeap.add(1);
        maxHeap.add(4);
        maxHeap.add(2);
        // 输出队列中的元素
        while (!maxHeap.isEmpty()) {
            System.out.println(maxHeap.poll()); // 输出最大元素，即5、4、3、2、1
        }
    }
}

在上面的示例中，我们创建了一个名为MaxHeapPriorityQueue的类，其中包含一个main()方法来演示如何使用PriorityQueue实现大顶堆。我们首先创建了一个自定义比较器maxHeapComparator，它将用于定义大顶堆的比较逻辑。然后，我们使用maxHeapComparator作为参数创建了一个PriorityQueue对象maxHeap。接下来，我们向maxHeap中添加了一些元素。最后，我们使用poll()方法逐个输出maxHeap中的元素。由于maxHeap是一个大顶堆，因此输出的元素将按照从大到小的顺序排列。

需要注意的是，在使用PriorityQueue实现大顶堆时，我们需要自定义比较器以改变默认的小顶堆行为。此外，由于Java中的PriorityQueue是基于数组实现的，因此在大顶堆中插入和删除元素的时间复杂度为O(log n)，其中n是队列中元素的数量。

Java优先级队列：实现大堆

最热文章