数据结构--优先队列

优先队列：

出队顺序和入队顺序无关，与优先级相关。动态选择优先级高的先处理(动态数据)。

实现优先队列

public class PriorityQueue<E extends Comparable<E>> implements Queue<E>{

    private MaxHeap<E> maxHeap;

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

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

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

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

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

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

相关示例

    // 215 数组中的第K个最大元素
    public int findKthLargest(int[] nums, int k) {
        //默认为最小堆
        PriorityQueue<Integer> pq = new PriorityQueue<>();

        for (int i = 0; i < k; i++) {
            pq.add(nums[i]);
        }

        for (int i = k; i < nums.length; i++) {
            //判断剩余元素中存不存在值大于 最小堆中的堆顶(最小元素)
            if (!pq.isEmpty() && nums[i] > pq.peek()){
                pq.remove();
                pq.add(nums[i]);
            }
        }

        return pq.peek();
    }

    // 剑指41 最小的k个数 二叉堆
    public int[] getLeastNumbers(int[] nums, int k) {
        //转成最大堆
        PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());

        for (int i = 0; i < k; i++) {
            pq.add(nums[i]);
        }

        for (int i = k; i < nums.length ; i++) {
            if (!pq.isEmpty() && nums[i] < pq.peek()) {
                pq.remove();
                pq.add(nums[i]);
            }
        }

        int[] res = new int[k];
        for (int i = 0; i < k; i++) {
            res[i] = pq.remove();
        }
        return res;
    }

top k 和select k的问题既可以用快排解决也可以用优先队列解决。

优先队列的优势：不需要一次性知道所有数据，适用于数据流，或者极大规模数据。

稳定性

排序前相等的俩个元素，排序后相对位置不变。
不稳定 排序是交换最后一个元素与做大元素。