java中的PriorityQueue即优先队列,底层通过数组存储的方式实现了小顶堆
一、PriorityQueue的使用
1.PriorityQueue与其他数据结构的关系
(1)PriorityQueue与其他集合数据结构的继承关系
(2)PriorityQueue实现的方法
2.PriorityQueue的使用
(1)实例化
- new PriorityQueue():使用默认容量和比较器
- new PriorityQueue(int capacity):指定队列的初始化容量
- new PriorityQueue(Comparator<? super E> comparator):指定一个比较器comparator来初始化队列
- new PriorityQueue(int capaicty, Comparator comparator):同时指定初始化容量和比较器
- new PriorityQueue(Collection c):通过一个集合来初始化
- new PriorityQueue(PriorityQueue p):通过另外一个优化队列进行初始化
- new PriorityQueue(SortedSet s):通过一个有序队列来初始化
/**
* 1.不指定容量和比较器初始化
*/
PriorityQueue<Integer> queue1 = new PriorityQueue<Integer>();
/**
* 2.指定容量初始化
*/
PriorityQueue<Integer> queue2 = new PriorityQueue<Integer>(10);
//只需要实现Comparator的compare方法即可
NumberComparator numberComparator = new NumberComparator();
/**
* 3.通过指定一个比较器初始化
*/
PriorityQueue<Integer> queue3 = new PriorityQueue<Integer>(numberComparator);
(2)添加元素
- add(E e):添加元素e (offer方法也是添加元素)
queue1.add(12);
queue1.add(1);
System.out.println(queue1); //[1, 12]
queue1.add(13);
System.out.println(queue1); //[1, 12, 13]
(3)删除元素
- remove() :删除堆的顶(和poll方法是一样的功能)
- remove(T e):删除指定元素
int removeElement = queue1.remove();
System.out.println(removeElement); //1
System.out.println(queue1); //[12, 13]
二、PriorityQueue的实现原理解读
1.PriorityQueue对象
PriorityQueue对象的属性
- queue : 存储数据的数组
- comparator : 比较器对象
- size : 队列长度
2.add方法
public boolean add(E e) {
//通过调用offer方法来实现的
return offer(e);
}
public boolean offer(E e) {
//添加的元素不能为null
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函数来进行元素插入
siftUp(i, e);
return true;
}
private void siftUp(int k, E x) {
//如果指定的比较器,就使用比较器来插入
if (comparator != null)
siftUpUsingComparator(k, x);
else
//如果没有指定比较器,就使用默认的比较器来插入元素
siftUpComparable(k, x);
}
private void siftUpComparable(int k, E x) {
//将插入的元素变为一个可比较的对象
Comparable<? super E> key = (Comparable<? super E>) x;
//k为插入的位置(插入节点一直与其父节点进行比较,直到父节点比插入节点小为止)
while (k > 0) {
//定义插入的节点的父节点的位置
int parent = (k - 1) >>> 1;
//获取父节点的元素值
Object e = queue[parent];
//如果插入的值比父节点的值要大,则跳出循环(因为是小顶堆,所以,父节点一定比子节点大,如果父节点比子节点小的话,则需要交换父亲子节点)
if (key.compareTo((E) e) >= 0)
break;
//如果父节点比当前插入的节点值大的话,那么就需要和当前要插入的节点位置进行互换,则当前k的值存储父节点
queue[k] = e;
//k的值为原父节点的位置
k = parent;
}
//获取最终节点插入的位置,并存储新元素到这个位置上
queue[k] = key;
}
private void siftUpUsingComparator(int k, E x) {
//k为插入的位置(插入节点一直与其父节点进行比较,直到父节点比插入节点小为止)
while (k > 0) {
//定义插入的节点的父节点的位置
int parent = (k - 1) >>> 1;
//获取父节点的元素值
Object e = queue[parent];
//使用指定的比较器来比较插入元素和当前的插入点的父节点元素(比较器都需要实现compare接口)
if (comparator.compare(x, (E) e) >= 0)
break;
//如果父节点比当前插入的节点值大的话,那么就需要和当前要插入的节点位置进行互换,则当前k的值存储
queue[k] = e;
//k的值为原父节点的位置
k = parent;
}
//获取最终节点插入的位置,并存储新元素到这个位置上
queue[k] = x;
}
3.remove方法
```java
public E remove() {
//调用poll方法删除元素
E x = poll();
if (x != null)
return x;
else
throw new NoSuchElementException();
}
public E poll() {
//如果是空队列,直接返回null
if (size == 0)
return null;
//队列长度减小,并且将s指向最后一个元素
int s = —size;
modCount++;
//获取队列的第一个元素
E result = (E) queue[0];
//获取队列的最后一个元素
E x = (E) queue[s];
//将队列的最后一个位置指向null,即删除最后一个节点
queue[s] = null;
//如果队列原来不只一个元素,使用siftDown来删除节点
if (s != 0)
siftDown(0, x);
//默认是删除第一个节点,则返回第一个节点的元素值
return result;
}
private void siftDown(int k, E x) {
if (comparator != null)
//使用指定的比较器来删除元素
siftDownUsingComparator(k, x);
else
//使用默认的比较器来删除元素
siftDownComparable(k, x);
}
private void siftDownComparable(int k, E x) {
//定义要删除的元素
Comparable<? super E> key = (Comparable<? super E>)x;
//获取中间节点位置
int half = size >>> 1;
while (k < half) {
//删除位置k所在的子节点位置
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];
//如果删除的元素的值比子节点的要小,那么不再交换位置
if (key.compareTo((E) c) <= 0)
break;
//交换父子节点的位置
queue[k] = c;
k = child;
}
//最后找到被删除的节点的位置,将原最后一个节点存入到这个位置上
queue[k] = key;
}