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

小程序：扫一扫查出行
【扫一扫了解最新限行尾号】
复制小程序

优先级队列

一、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];
}

删除头部元素：略