优先队列

优先队列

基于堆的优先队列

public class PriorityQueue<E extends Comparable<E>>{
    
    private MaxHeap<E> maxHeap;

    public PriorityQueue(){
        maxHeap = new MaxHeap();
    }

    public int getSize(){
        return maxHeap.size();
    }

    public boolean isEmpty(){
        return maxHeap.isEmpty();
    }

    public E getFront(){
        return maxHeap.findMax();
    }

    public void enqueue(E e){
        maxHeap.add(e);
    }

    public E dequeue(){
        return maxHeap.extractMax();
    }
}

应用

• top K问题,在N个元素中选出最小的K个元素

  public int[] getLeastNumbers(int[] arr,int k){
    PriorityQueue<Integer> pq = new PriorityQueue<>();
    for(int i=0;i<k;i++){
        pq.enqueue(arr[i])
    }
  
    for(int i=k;i<arr.length;i++){
        if(!pq.isEmpty()&&arr[i]<pq.getFront()){
            pq.dequeue();
            pq.enqueue(arr[i]);
        }
    }
    int[] res = new int[k];
    for(int i=0;i<k;i++){
        res[i]=pq.dequeue();
    }
    return res
  }