优先队列

1.优先队列

2.优先队列的实现

public interface Queue<E> {
    int getSize();
    Boolean isEmpty();
    void enqueue(E e);
    E dequeue();
    E getFront();
}

2.1 使用堆实现

// 使用堆实现优先队列
public class PriorityQueue <E extends Comparable<E>> implements Queue<E>{
    private MaxHeap<E> data;
    // 若传入数组，可以直接使用堆进行堆化
    public PriorityQueue(){
        data = new MaxHeap<>();
    }
    @Override
    public int getSize(){
        return data.getSize();
    }
    @Override
    public boolean isEmpty(){
        return data.isEmpty();
    }
    @Override
    // O(h)
    public void enqueue(E e){
        data.add(e);
    }
    @Override
    // O(h) h 为 树的高度
    public E dequeue(){
        return data.remove();
    }
    @Override
    // O(1)
    public E getFront(){
        return data.findMax();
    }
}

2.2使用LinkedList实现

// 使用LinkedList实现
// 对于优先队列，需要在尾部加入，头部删除
// 所以 enqueue 为 O(1)
public class  PriorityQueue <E extends Comparable<E>> implements Queue<E>{
    private Linkedlist<E> data;
    // 将数组放入，实现队列，由于链表的 add 不存在
    public PriorityQueue(E[] arr){
        //先将数组排序
        QuickSort.sort(arr);
        data = new LinkedList<>();
        for(int i = 0; i < arr.length; i++){
            data.addFirst(arr[i]);
        }
    }
    @Override
    public int getSize(){
        return data.getSize();
    }
    @Override
    public Boolean isEmpty(){
        return data.isEmpty();
    }
    @Override
    public void enqueue(E e){
         // 这里需要进行比较，找到元素在 链表中的位置，再使用add(e, index)
        // 在 index 处插入
        data.sort(e);
    }
    // 对链表进行排序
    public void sort(E value){
        E target = value;
        Node prev = dummyHead;
        for(int i = 0; i < size; i++){
            prev = prev.next;
            if(target.compareTo(prev.e) >= 0){
                add(i,target);
                break;
            }
        }
    }
    @Override
    public E dequeue(){
        E res = data.getFront();
        data.removeFirst();
        return res;
    }
    @Override
    public E getFront(){
        return data.getFront();
    }
}

2.3 使用数组实现

// 使用 可变数组实现
public class  PriorityQueue <E extends Comparable<E>> implements Queue<E>{
    private Array<E> data;
    // 将数组放入，实现队列，由于链表的 add 不存在
    public PriorityQueue(E[] arr){
        //先将数组排序
        QuickSort.sort(arr);
        data = new Array<>();
        // 从大到小
        for(int i = 0; i < arr.length; i++){
            data.addFirst(arr[i]);
        }
    }
    @Override
    public int getSize(){
        return data.getSize();
    }
    @Override
    public Boolean isEmpty(){
        return data.isEmpty();
    }
    @Override
    public void enqueue(E e){
         // 这里需要进行比较，找到元素在 链表中的位置，再使用add(e, index)
        // 在 index 处插入
        for(int i = 0; i < data.getSize();i++){
            if(data.get(i).compareTo(e) <= 0){
                data.add(i,e);
                break;
            }
        }
    }
    @Override
    public E dequeue(){
        E res = data.getFront();
        data.removeFirst();
        return res;
    }
    @Override
    public E getFront(){
        return data.getFront();
    }
}

3.leetcode 相关问题

1.topK 问题：

取出最大或者最小的k个元素
https://leetcode-cn.com/problems/zui-xiao-de-kge-shu-lcof/

class Solution {
    public int[] getLeastNumbers(int[] arr, int k) {
        // 优先队列默认最小堆
        Queue<Integer> queue = new PriorityQueue<>(Collections.reverseOrder());
        // 由于优先队列在add时会进行排序，所以会由大到小进行排序
        for(int nu: arr){
            queue.add(nu);
        }
        int[] res = new int[k];
        for(int i = 0; i < k ; i++){
            res[i] = queue.remove();
        }
        return res;
    }
}
//优化
// 先任意加入 k 个元素，最大的在前面，一旦有小于最大的就加入

2. SelectK 问题

// 使用优先队列
class Solution {
    public int findKthLargest(int[] nums, int k) {
        // 默认最小堆
        Queue<Integer> queue = new PriorityQueue<>();
        // 加入前k个数
        for(int i = 0; i < k; i++){
            queue.add(nums[i]);
        }
        // 然后遍历后面的元素，假如有数比这个大，则插入
        // 最后队列的顶就是第k大的值（加入过程中会进行排序）
        for(int i = k ; i < nums.length; i++){
            while(!queue.isEmpty() && nums[k] > queue.peek()){
                queue.remove();
                queue.add(nums[k]);
            }
        }
    }
}

4.对于不同的队列：

Java 实现的标准优先队列：

若没有传入比较器，则默认最小堆，否则为最大堆