优先级队列

一、PriorityQueue

PriorityQueue是优先级队列，它实现了Queue接口，它的队列长度

没有限制，与一般队列的区别是，它有优先级概念，每个元素都有优先

级，队头的元素永远都是优先级最高的。PriorityQueue内部是用堆实现的。

一、基本用法

主要构造方法:

public PriorityQueue()

public PriorityQueue(int initialCapacity, Comparator<? super E> comparator)

public PriorityQueue(Collection<? extends E> c) //动态数组大小等于容器中元素的个数

PriorityQueue使用动态数组initialCapacity表示初始数组的大小。举例：

PriorityQueue<Integer> ints = new PriorityQueue<>();

ints.offer(10);

ints.add(28);

ints.addAll(Arrays.asList(22, 33, 55, 66));

while (ints.peek() != null) {

    System.out.println(ints.poll() + "  ");

}

二、实现原理

内部成员：

private transient Object[] queue;

private int size = 0;

private final Comparator<? super E> comparator;

private transient int modCount = 0;

构造方法：

public PriorityQueue() {

    this(DEFAULT_INITIAL_CAPACITY, null);

}

public PriorityQueue(int initialCapacity) {

    this(initialCapacity, null);

}

public PriorityQueue(int initialCapacity,

                     Comparator<? super E> comparator) {

    if(initialCapacity < 1)

        throw new IllegalArgumentException();

    this.queue = new Object[initialCapacity];

    this.comparator = comparator;

}

添加元素的代码

public boolean offer(E e) {

    if(e == null)

        throw new NullPointerException();

    modCount++;

    int i = size;

    if(i >= queue.length) //先确保数组长度是否足够，如果不够，用grow方法扩展઀

        grow(i + 1);

    size = i + 1;

    if(i == 0) //如果是第一次添加

        queue[0] = e;

    else //否则将其放入最后一个位置，并向上调整

        siftUp(i, e);return true;

}

private void grow(int minCapacity) {

    int oldCapacity = queue.length;

   // Double size if small; else grow by 50%

    int newCapacity = oldCapacity + ((oldCapacity < 64)

    (oldCapacity + 2) :

    (oldCapacity >> 1));

    // overflow-conscious code

    if(newCapacity - MAX_ARRAY_SIZE > 0)

        newCapacity = hugeCapacity(minCapacity);

    queue = Arrays.copyOf(queue, newCapacity);

}

private void siftUp(int k, E x) {

    if(comparator != null)

        siftUpUsingComparator(k, x);

    else

        siftUpComparable(k, x);

}

private void siftUpUsingComparator(int k, E x) {

    while(k > 0) {

        int parent = (k - 1) >>> 1;

        Object e = queue[parent];

        if(comparator.compare(x, (E) e) >= 0)

            break;

        queue[k] = e;

        k = parent;

    }

    queue[k] = x;

}

查看元素头部元素：

public E peek() {

    if(size == 0)

        return null;

    return (E) queue[0];

}

删除头部元素：略

三、总结

1）实现了优先级队列，最先出队的总是优先级最高的，即排序中的第一个。

2）优先级可以有相同的，内部元素不是完全有序的，如果遍历输出，除了第一个其他没有特定顺序。、

3）查看头部元素，入队出队的效率都很高

4）根据值查找和删除元素的效率很低。

巴特西

Java笔记（十）堆与优先级队列

优先级队列

一、PriorityQueue

一、基本用法

二、实现原理

三、总结

最新文章

热门文章