大家好,又见面了,我是你们的朋友全栈君。
来源:
Java编程的逻辑
1 前导
将新的头部与两个孩子节点中较小的比较,如果不大于该孩子节点,则满足堆的性质,结束,否则与较小的孩子进行交换,交换后,再与较小的孩子比较和交换,一直到没有孩子,或者不大于两个孩子节点。这个过程我们般称为siftdown
与父节点比较,如果大于等于父节点,则满足堆的性质,结束,否则与父节点进行交换,然后再与父节点比较和交换,直到父节点为空或者大于等于父节点;称之为siftup
2 实现原理
PriorityQueue是优先级队列,它首先实现了队列接口(Queue),与LinkedList类似,它的队列长度也没有限制,与一般队列的区别是,它有优先级的概念,每个元素都有优先级,队头的元素永远都是优先级最高的。
PriorityQueue内部是用堆实现的,内部元素不是完全有序的,不过,逐个出队会得到有序的输出。
虽然名字叫优先级队列,但也可以将PriorityQueue看做是一种比较通用的实现了堆的性质的数据结构,可以用PriorityQueue来解决适合用堆解决的问题
2.1 Queue接口
public interface Queue<E> extends Collection<E> {
boolean add(E e);
boolean offer(E e);
E remove();
E poll();
E element();
E peek();
}
2.2 构造方法
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;
}
PriorityQueue是用堆实现的,堆物理上就是数组,与ArrayList类似,PriorityQueue同样使用动态数组,根据元素个数动态扩展,initialCapacity表示初始的数组大小,可以通过参数传入。对于默认构造方法,initialCapacity使用默认值11。对于最后三个构造方法,它们接受一个已有的Collection,数组大小等于参数容器中的元素个数。
与TreeMap/TreeSet类似,为了保持一定顺序,PriorityQueue要求,要么元素实现Comparable接口,要么传递一个比较器Comparator
2.3 内部组成
private transient Object[] queue//实际存储元素的数组
private int size = 0;//当前元素个数
private final Comparator<? super E> comparator;
private transient int modCount = 0;
2.4 入队
public boolean offer(E e) {
if (e == null)
throw new NullPointerException();
modCount++;
int i = size;
if (i >= queue.length)
grow(i + 1);//动态扩展
size = i + 1;
if (i == 0)
queue[0] = e;
else
siftUp(i, e);//放入最后一个位置,向上调整
return true;
}
//如果原长度比较小,扩展为2oldCapacity+2,否则就是增加50%,使用Arrays.copyOf方法拷贝数组
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));
// newCapacity溢出时,就变为Integer.MAX_VALUE或MAX_ARRAY_SIZE
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
queue = Arrays.copyOf(queue, newCapacity);
}
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE;
}
//新元素(x)不断与父节点(e)比较,如果新元素(x)大于等于父节点(e),则已满足堆的性质,退出循环,k就是新元素最终的位置;
//否则,将父节点往下移(queue[k]=e),继续向上寻找(k=parent)
private void siftUp(int k, E x) {
if (comparator != null)
siftUpUsingComparator(k, x);
else
siftUpComparable(k, x);
}
@SuppressWarnings("unchecked")
private void siftUpComparable(int k, E x) {
Comparable<? super E> key = (Comparable<? super E>) x;
while (k > 0) {
int parent = (k - 1) >>> 1;
Object e = queue[parent];
if (key.compareTo((E) e) >= 0)
break;
queue[k] = e;
k = parent;
}
queue[k] = key;
}
@SuppressWarnings("unchecked")
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;
}
2.5 查看头部元素
public E peek() {
if (size == 0)
return null;
return (E) queue[0];
}
2.6 删除头部元素
//返回结果result为第一个元素,x指向最后一个元素,将最后位置设置为null (queue[s] = null)
//最后调用siftDown将原来的最后元素x插入头部并调整堆
public E poll() {
if (size == 0)
return null;
int s = --size;
modCount++;
E result = (E) queue[0];
E x = (E) queue[s];
queue[s] = null;
if (s != 0)
siftDown(0, x);
return result;
}
//将原来的最后元素x插入头部并调整堆
private void siftDown(int k, E x) {
if (comparator != null)
siftDownUsingComparator(k, x);
else
siftDownComparable(k, x);
}
//新元素key不断与较小的孩子比较,如果小于等于较小的孩子,则已满足堆的性质,退出循环,k就是最终位置;
//否则将较小的孩子往上移,继续向下寻找
private void siftDownComparable(int k, E x) {
Comparable<? super E> key = (Comparable<? super E>)x;
int half = size >>> 1;
while (k < half) {
//编号为k的节点有孩子节点,则进入循环
//表示较小的孩子编号,假定为左孩子,如果有右孩子(编号right)且小于左孩子则child会变为right
int child = (k << 1) + 1;
Object c = queue[child];//较小的孩子节点
int right = child + 1;
if (right < size && ((Comparable<? super E>) c).compareTo((E) queue[right]) > 0)
c = queue[child = right];//k=child这一步就不用判断,直接赋值为child即可
if (key.compareTo((E) c) <= 0)
break;
queue[k] = c;//上移
k = child;//从新的节点继续寻找
}
queue[k] = key;
}
private void siftDownUsingComparator(int k, E x) {
int half = size >>> 1;
while (k < half) {
int child = (k << 1) + 1;
Object c = queue[child];
int right = child + 1;
if (right < size &&
comparator.compare((E) c, (E) queue[right]) > 0)
c = queue[child = right];
if (comparator.compare(x, (E) c) <= 0)
break;
queue[k] = c;
k = child;
}
queue[k] = x;
}
2.7 查找元素
public boolean contains(Object o) {
return indexOf(o) != -1;
}
private int indexOf(Object o) {
if (o != null) {
for (int i = 0; i < size; i++)
if (o.equals(queue[i]))
return i;
}
return -1;
}
2.8 根据值删除元素
//先查找元素的位置i,然后调用removeAt进行删除
public boolean remove(Object o) {
int i = indexOf(o);
if (i == -1)
return false;
else {
removeAt(i);
return true;
}
}
//如果是删除最后一个位置,直接删即可;
//否则移动最后一个元素moved到位置i并进行堆调整;
//调整有两种情况,如果大于孩子节点,则向下调整,否则如果小于父节点则向上调整
private E removeAt(int i) {
assert i >= 0 && i < size;
modCount++;
int s = --size;
if (s == i) //删除最后一个位置
queue[i] = null;
else {
E moved = (E) queue[s];
queue[s] = null;
siftDown(i, moved);//先向下调整试试
if (queue[i] == moved) {
//如果没有向下调整过
siftUp(i, moved);//则向上调整试试
if (queue[i] != moved)//如果向上调整过
return moved;//则返回moved
}
}
//其他情况返回null,即向下调整过,或没有调整过
//用于正确实现PriorityQueue迭代器的删除方法
return null;
}
2.9 构建初始堆
如果从一个既不是PriorityQueue也不是SortedSet的容器构造堆,代码为:
private void initFromCollection(Collection<? extends E> c) {
initElementsFromCollection(c);
heapify();
}
//主要是初始化queue和size。
private void initElementsFromCollection(Collection<? extends E> c) {
Object[] a = c.toArray();
if (a.getClass() != Object[].class)
a = Arrays.copyOf(a, a.length, Object[].class);
this.queue = a;
this.size = a.length;
}
//从最后一个非叶子节点开始,一直往前直到根;
//对每个节点,执行向下调整siftdown;
//也就是说,自底向上,先使每个最小子树为堆,然后每对左右子树和其父节点合并,调整为更大的堆,因为每个子树已经为堆,所以调整就是对父节点执行siftdown,就这样一直合并调整直到根
private void heapify() {
for (int i = (size >>> 1) - 1; i >= 0; i--)
siftDown(i, (E) queue[i]);
}
如果构造方法中的参数是PriorityQueue或SortedSet,则它们的toArray方法返回的数组就是有序的,就满足堆的性质,就不需要执行heapify了。
3 特点分析
PriorityQueue实现了Queue接口,有优先级,内部是用堆实现的,这决定了它有如下特点:
- 实现了优先级队列,最先出队的总是优先级最高的,即排序中的第一个。
- 优先级可以有相同的,内部元素不是完全有序的,如果遍历输出,除了第一个,其他没有特定顺序。
- 查看头部元素的效率很高,为O(1),入队、出队效率比较高,为O(log2(N)),构建堆heapify的效率为O(N)。
- 根据值查找和删除元素的效率比较低,为O(N)。
发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/133616.html原文链接:https://javaforall.cn
【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛
【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...