Java 浅谈PriorityQueue常用方法的时间复杂度（通过源码分析）

复杂度（通过源码分析）"/>

Java 浅谈PriorityQueue常用方法的时间复杂度（通过源码分析）

介绍

PriorityQueue，也叫优先队列，是一个通过完全二叉树实现的小顶堆。
其作用是每次以O(1)取出队列中权值最小的元素,再以O(log)维护队列

构造

默认无参构造小顶堆（维护队列中最小的元素）

Queue<Integer> q = new PriorityQueue<Integer>();

Collections的reverseOrder方法实现了自然排序的相反排序，返回一个比较器，以此来构造大顶堆（维护队列中最大的元素）

Queue<Integer> q = new PriorityQueue<>(Collections.reverseOrder());

（ps：构造大顶堆的方式多种多样，这里写一种我看到的，比较秀比较简便的方式）

方法时间复杂度分析

1、boolean add(E e)

——将指定的元素插入到此优先级队列中。O(logN)

	public boolean add(E e) {return offer(e);}

可以看到add方法就是直接调用offer方法

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;elsesiftUp(i, e);return true;}

offer方法用来在数据中添加一个元素，维护的时间复杂度是O(log)，
所以总的时间复杂度就是O(log)。

2、boolean contains(Object o)

——是否包含指定元素，包含返回 true。O(n)

	public boolean contains(Object o) {return indexOf(o) != -1;}

方法直接调用indexOf方法查找指定元素索引，根据索引判断是否包含

	private int indexOf(Object o) {if (o != null) {for (int i = 0; i < size; i++)if (o.equals(queue[i]))return i;}return -1;}

从源码中可以看到，查找索引是遍历一遍数组，时间是O(n)。
所以总的时间复杂度是O(n).

3、E peek()

——检索但不删除此队列的头，如果此队列为空，则返回 null 。O（1）

	public E peek() {return (size == 0) ? null : (E) queue[0];}

peek方法直接返回队头的值，所以总的时间复杂度是O(1)。

4、E poll()

——检索并删除此队列的头，如果此队列为空，则返回 null 。O(logN)

	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;}

删除队头元素维护堆的时间是O(log),所以总的时间是O(log)。

5、boolean remove(Object o)

——从该队列中删除指定元素的单个实例（如果存在）。O(n)

	public boolean remove(Object o) {int i = indexOf(o);if (i == -1)return false;else {removeAt(i);return true;}}

remove方式是先通过indexOf方法查找到指定元素的索引，再通过removeAt传入索引删除元素。

	private int indexOf(Object o) {if (o != null) {for (int i = 0; i < size; i++)if (o.equals(queue[i]))return i;}return -1;}private E removeAt(int i) {// assert i >= 0 && i < size;modCount++;int s = --size;if (s == i) // removed last elementqueue[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;}}return null;}

可以看出indexOf方法遍历了一遍数组，时间复杂度为O(n),
removeAt方法删除元素维护堆结构，时间复杂度为O(log),
所以总的时间复杂度为O(n)。
特别注意：这个remove方法只能删除一个指定元素，不是全部

6、int size()

——返回此集合中的元素个数。O(1)

	public int size() {return size;}

直接返回一个size属性，所以总的时间复杂度是O(1)