优先级队列

◼ 优先级队列也是个队列,因此也是提供以下接口
◼ int size(); // 元素的数量
◼ boolean isEmpty(); // 是否为空
◼ void enQueue(E element); // 入队
◼ E deQueue(); // 出队
◼ E front(); // 获取队列的头元素
◼ void clear(); // 清空
◼ 普通的队列是 FIFO 原则,也就是先进先出
◼ 优先级队列则是按照优先级高低进行出队,比如将优先级最高的元素作为队头优先出队

优先队列的底层实现
◼ 根据优先队列的特点,很容易想到:可以直接利用二叉堆作为优先队列的底层实现
◼ 可以通过 Comparator 或 Comparable 去自定义优先级高低

优先级队列

Java官方的优先级队列priorityQueue底层是用最小堆实现的,详情可以看他的下滤和上滤操作。因此调用其poll方法,返回结果是该队列中最小的元素。

Java官方的一个上滤方法

private static <T> void siftUpComparable(int k, T x, Object[] es) {
        Comparable<? super T> key = (Comparable<? super T>) x;
        while (k > 0) {
            int parent = (k - 1) >>> 1;
            Object e = es[parent];
            if (key.compareTo((T) e) >= 0)
                break;
            es[k] = e;
            k = parent;
        }
        es[k] = key;
    }
上一篇:数据结构与算法之堆排序


下一篇:Java 比较器