Java数据结构之堆(优先队列)PriorityQueue的使用及实现解读

java中的PriorityQueue即优先队列,底层通过数组存储的方式实现了小顶堆

一、PriorityQueue的使用

1.PriorityQueue与其他数据结构的关系
(1)PriorityQueue与其他集合数据结构的继承关系

PriorityQueue与其他集合数据结构的继承关系

(2)PriorityQueue实现的方法

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. /**
  2. * 1.不指定容量和比较器初始化
  3. */
  4. PriorityQueue<Integer> queue1 = new PriorityQueue<Integer>();
  5. /**
  6. * 2.指定容量初始化
  7. */
  8. PriorityQueue<Integer> queue2 = new PriorityQueue<Integer>(10);
  9. //只需要实现Comparator的compare方法即可
  10. NumberComparator numberComparator = new NumberComparator();
  11. /**
  12. * 3.通过指定一个比较器初始化
  13. */
  14. PriorityQueue<Integer> queue3 = new PriorityQueue<Integer>(numberComparator);
(2)添加元素
  • add(E e):添加元素e (offer方法也是添加元素)
  1. queue1.add(12);
  2. queue1.add(1);
  3. System.out.println(queue1); //[1, 12]
  4. queue1.add(13);
  5. System.out.println(queue1); //[1, 12, 13]
(3)删除元素
  • remove() :删除堆的顶(和poll方法是一样的功能)
  • remove(T e):删除指定元素
  1. int removeElement = queue1.remove();
  2. System.out.println(removeElement); //1
  3. System.out.println(queue1); //[12, 13]

二、PriorityQueue的实现原理解读

1.PriorityQueue对象

PriorityQueue对象的属性

  • queue : 存储数据的数组
  • comparator : 比较器对象
  • size : 队列长度
2.add方法
  1. public boolean add(E e) {
  2. //通过调用offer方法来实现的
  3. return offer(e);
  4. }
  5. public boolean offer(E e) {
  6. //添加的元素不能为null
  7. if (e == null)
  8. throw new NullPointerException();
  9. modCount++;
  10. //先定义插入的位置,为队列的长度
  11. int i = size;
  12. //如果实际队列占用的长度已经超过数组最大的容量,则需要扩容
  13. if (i >= queue.length)
  14. grow(i + 1);
  15. //增加队列的长度
  16. size = i + 1;
  17. //如果队列本来就为空队列,那么插入的元素就是队列的第一个元素
  18. if (i == 0)
  19. queue[0] = e;
  20. else
  21. //否则,就要通过siftUp函数来进行元素插入
  22. siftUp(i, e);
  23. return true;
  24. }
  25. private void siftUp(int k, E x) {
  26. //如果指定的比较器,就使用比较器来插入
  27. if (comparator != null)
  28. siftUpUsingComparator(k, x);
  29. else
  30. //如果没有指定比较器,就使用默认的比较器来插入元素
  31. siftUpComparable(k, x);
  32. }
  33. private void siftUpComparable(int k, E x) {
  34. //将插入的元素变为一个可比较的对象
  35. Comparable<? super E> key = (Comparable<? super E>) x;
  36. //k为插入的位置(插入节点一直与其父节点进行比较,直到父节点比插入节点小为止)
  37. while (k > 0) {
  38. //定义插入的节点的父节点的位置
  39. int parent = (k - 1) >>> 1;
  40. //获取父节点的元素值
  41. Object e = queue[parent];
  42. //如果插入的值比父节点的值要大,则跳出循环(因为是小顶堆,所以,父节点一定比子节点大,如果父节点比子节点小的话,则需要交换父亲子节点)
  43. if (key.compareTo((E) e) >= 0)
  44. break;
  45. //如果父节点比当前插入的节点值大的话,那么就需要和当前要插入的节点位置进行互换,则当前k的值存储父节点
  46. queue[k] = e;
  47. //k的值为原父节点的位置
  48. k = parent;
  49. }
  50. //获取最终节点插入的位置,并存储新元素到这个位置上
  51. queue[k] = key;
  52. }
  53. private void siftUpUsingComparator(int k, E x) {
  54. //k为插入的位置(插入节点一直与其父节点进行比较,直到父节点比插入节点小为止)
  55. while (k > 0) {
  56. //定义插入的节点的父节点的位置
  57. int parent = (k - 1) >>> 1;
  58. //获取父节点的元素值
  59. Object e = queue[parent];
  60. //使用指定的比较器来比较插入元素和当前的插入点的父节点元素(比较器都需要实现compare接口)
  61. if (comparator.compare(x, (E) e) >= 0)
  62. break;
  63. //如果父节点比当前插入的节点值大的话,那么就需要和当前要插入的节点位置进行互换,则当前k的值存储
  64. queue[k] = e;
  65. //k的值为原父节点的位置
  66. k = parent;
  67. }
  68. //获取最终节点插入的位置,并存储新元素到这个位置上
  69. queue[k] = x;
  70. }
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;
}