PriorityQueue如何实现大小顶堆

PriorityQueue可以通过传入Comparator参数来实现大小顶堆。Comparator可以被定义为比较函数，用于比较PriorityQueue中的元素顺序。比较函数可以实现升序或降序排列，以便PriorityQueue可以按照特定的顺序将其元素保存在队列中。如果定义比较函数来实现逆序排列，那么PriorityQueue将成为一个最大堆或大顶堆，而如果定义比较函数来实现正序排列，那么PriorityQueue将成为一个最小堆或小顶堆。在Java中实现大小顶堆的代码片段如下：

// 创建一个大小顶堆，使用默认的比较函数来实现升序排列
PriorityQueue<Integer> minHeap = new PriorityQueue<>();

// 创建一个大小顶堆，使用自定义的比较函数来实现降序排列
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Comparator.reverseOrder());

// 添加元素到大小顶堆中
minHeap.add(5);
minHeap.add(2);
minHeap.add(10);
maxHeap.add(5);
maxHeap.add(2);
maxHeap.add(10);

// 获取大小顶堆的堆顶元素
int minTop = minHeap.peek();
int maxTop = maxHeap.peek();

// 删除大小顶堆的堆顶元素
minHeap.poll();
maxHeap.poll();

相关问题

java实现大顶堆

在Java中可以使用PriorityQueue（优先队列）来实现大顶堆。

PriorityQueue是一个基于优先级的无界优先队列，它的元素按照自然顺序进行排序，或者根据构造函数中传递的Comparator进行排序。它是线程不安全的，不能保证队列中的元素是按照优先级的顺序排列的。

下面是使用PriorityQueue实现大顶堆的示例代码：

import java.util.PriorityQueue;

public class MaxHeap {
    public static void main(String[] args) {
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>((a, b) -> b - a);
        maxHeap.offer(3);
        maxHeap.offer(1);
        maxHeap.offer(5);
        maxHeap.offer(2);
        maxHeap.offer(4);
        while (!maxHeap.isEmpty()) {
            System.out.print(maxHeap.poll() + " ");
        }
    }
}

输出结果为：5 4 3 2 1

在这个示例中，我们创建了一个PriorityQueue对象，并传递了一个Comparator来实现大顶堆。然后我们向队列中添加了一些元素，最后按照优先级（即值大小）从大到小依次取出元素并输出。

java实现有限长度的小顶堆

Java中可以通过优先队列（PriorityQueue）来实现小顶堆。默认情况下，PriorityQueue是一个小顶堆，也就是说每次取出队列中的元素都是当前队列中最小的元素。

但是，PriorityQueue的默认实现是无限长度的，如果要实现有限长度的小顶堆，需要在初始化PriorityQueue时设置其容量大小，并在插入元素时判断队列是否已满，如下所示：

import java.util.PriorityQueue;

public class MinHeap {
    private PriorityQueue<Integer> pq;
    private int capacity;

    public MinHeap(int capacity) {
        this.capacity = capacity;
        pq = new PriorityQueue<>(capacity);
    }

    public void add(int val) {
        if (pq.size() < capacity) {
            pq.add(val);
        } else if (val < pq.peek()) {
            pq.poll();
            pq.add(val);
        }
    }

    public int[] toArray() {
        int[] res = new int[capacity];
        int i = 0;
        for (int num : pq) {
            res[i++] = num;
        }
        return res;
    }
}

在上面的代码中，我们将有限长度的小顶堆封装在了一个MinHeap类中，其中capacity为堆的容量大小，add方法用于往堆中添加元素，toArray方法用于将堆中的元素转换成数组输出。

在add方法中，我们首先判断堆是否已满，如果未满则直接添加元素；如果已满，则判断新添加的元素是否比堆顶元素小，如果是，则弹出堆顶元素并添加新元素。

最后，我们可以通过调用toArray方法将堆中的元素转换成数组输出。