Java中的集合（四）PriorityQueue常⽤⽅法
Java中的集合（四）PriorityQueue常⽤⽅法PriorityQueue的基本概念等都在上⼀篇已说明，感兴趣的可以点击查看
这⾥主要以PriorityQueue的常⽤⽅法的学习
⼀、PriorityQueue的实现
从上图中给层序遍历编号，从中可以发现⽗⼦节点总有如下的关系：
通过上述三个公式，可以轻易计算出某个节点的⽗节点以及⼦节点的下标。这也就是为什么可以直接⽤数组来存储堆的原因。
PriorityQueue的peek()和element()操作是常数时间，add()、offer()、⽆参数的remove()以及poll()⽅法的时间复杂度都是log(N)。⼆、PriorityQueue常⽤的⽅法
三、常⽤⽅法剖析
（⼀）插⼊元素：add(E e)和offer(E e)
add（E e）和offer（E e）两者的语义是相同，都是往优先队列中插⼊元素，只是Queue接⼝规定了两者对插⼊失败时采取不同的处理⽅式。add（E e）⽅法插⼊元素失败时会抛出异常，offer（E e）插⼊元素失败时会返回false，对PriorityQueue⽽⾔，两者没有什么区别。
1public boolean add(E e) {
2return offer(e); // add⽅法内部调⽤offer⽅法
3 }
4public boolean offer(E e) {
5if (e == null) // 元素为空的话，抛出NullPointerException异常
6throw new NullPointerException();
7 modCount++;
8int i = size;
9if (i >= queue.length) // 如果当前⽤堆表⽰的数组已经满了，调⽤grow⽅法扩容
10 grow(i + 1); // 扩容
11 size = i + 1; // 元素个数+1
12if (i == 0) // 堆还没有元素的情况
13 queue[0] = e; // 直接给堆顶赋值元素
14else// 堆中已有元素的情况
15 siftUp(i, e); // 重新调整堆，从下往上调整，因为新增元素是加到最后⼀个叶⼦节点
16return true;
17 }
18private void siftUp(int k, E x) {
19if (comparator != null) // ⽐较器存在的情况下
20 siftUpUsingComparator(k, x); // 使⽤⽐较器调整
21else// ⽐较器不存在的情况下
22 siftUpComparable(k, x); // 使⽤元素⾃⾝的⽐较器调整
23 }
24private void siftUpUsingComparator(int k, E x) {
25while (k > 0) { // ⼀直循环直到⽗节点还存在
26int parent = (k - 1) >>> 1; // 到⽗节点索引，等同于（k - 1）/ 2
27 Object e = queue[parent]; // 获得⽗节点元素
28// 新元素与⽗元素进⾏⽐较，如果满⾜⽐较器结果，直接跳出，否则进⾏调整
29if (comparatorpare(x, (E) e) >= 0)
30break;
31 queue[k] = e; // 进⾏调整，新位置的元素变成了⽗元素
32 k = parent; // 新位置索引变成⽗元素索引，进⾏递归操作
33 }
34 queue[k] = x; // 新添加的元素添加到堆中
35 }
View Code
下⾯根据图解演⽰插⼊元素过程：
（⼆）、获取元素但不删除队列⾸元素：element()和peek()
element()和peek()的语义是相同的，都是获取元素但不删除队列⾸元素，也就是队列中权值最下的元素，
只是Queue接⼝规定了两者删除元素失败时的不同处理⽅式，element()会抛出异常，peek()会返回null。根据⼩顶堆的特性，堆顶最上层的元素权值是最⼩的，由于是数组实现的，根据⼩标关系，⼩标0既是堆顶的元素，也是数组的第⼀个元素，所以直接返回下标为0的那个元素即可。
1// PriorityQueue的peek()
2public E peek() {
3if (size == 0)
4return null;
5return (E) queue[0];//0下标处的那个元素就是最⼩的那个
6 }
7
8// AbstractQueue的element()，由于PriorityQueue继承⾃AbstractQueue，所以可以使⽤element()⽅法
9public E element() {
10 E x = peek();
11if (x != null)
12return x;
13else
14throw new NoSuchElementException();
15 }
View Code
下⾯根据图解演⽰获取元素过程：
（三）、获取并删除队列⾸元素：remove()和poll()
element()和peek()的语义是相同的，都是获取元素并删除队列⾸元素，只是Queue接⼝规定了两者删除元素失败时的不同处理⽅
式，remove()会抛出异常，poll()会返回null。由于删除会影响队列的结构，所以会通过siftDown()和siftU
p()⽅法调整队列结构。
1public E poll() {
2if (size == 0)
3return null;
4int s = --size;
5 modCount++;
6 E result = (E) queue[0];//0下标处的那个元素就是最⼩的那个nullpointerexception为什么异常
7 E x = (E) queue[s];
8 queue[s] = null;
9if (s != 0)
10 siftDown(0, x);//调整
11return result;
12 }
13
14public E remove() {
15 E x = poll();
16if (x != null)
17return x;
18else
19throw new NoSuchElementException();
20 }
21
22private void siftDown(int k, E x) {
23if (comparator != null) // ⽐较器存在的情况下
24 siftDownUsingComparator(k, x); // 使⽤⽐较器调整
25else// ⽐较器不存在的情况下
26 siftDownComparable(k, x); // 使⽤元素⾃⾝的⽐较器调整
27 }
28private void siftDownUsingComparator(int k, E x) {
29int half = size >>> 1; // 只需循环节点个数的⼀般即可
30while (k < half) {
31int child = (k << 1) + 1; // 得到⽗节点的左⼦节点索引，即（k * 2）+ 1
32 Object c = queue[child]; // 得到左⼦元素
33int right = child + 1; // 得到⽗节点的右⼦节点索引
34if (right < size &&
35 comparatorpare((E) c, (E) queue[right]) > 0) // 左⼦节点跟右⼦节点⽐较，取更⼤的值
36 c = queue[child = right];
37if (comparatorpare(x, (E) c) <= 0) // 然后这个更⼤的值跟最后⼀个叶⼦节点⽐较
38break;
39 queue[k] = c; // 新位置使⽤更⼤的值
40 k = child; // 新位置索引变成⼦元素索引，进⾏递归操作
41 }
42 queue[k] = x; // 最后⼀个叶⼦节点添加到合适的位置
43 }
View Code
下⾯根据图解演⽰获取元素过程：
通过上述代码和图解可以看出：
1、⾸先记录0下标处的元素，并⽤最后⼀个元素替换0下标位置的元素，
2、调⽤siftDown()⽅法对堆进⾏调整，最后返回原来0下标处的那个元素（也就是最⼩的那个元素）。
重点是siftDown(int k，E e)⽅法，该⽅法的作⽤是从k指定的位置开始，将x逐层向下与当前点的左右孩⼦中较⼩的那个交换，直到x⼩于或等于左右孩⼦中的任何⼀个为⽌。
（四）、删除队列中的指定元素：remove(Object o)
remove(Object o)⽤于删除队列中的指定元素（如果队列中有多个相同元素，只删除⼀个），由于删除操作会改变队列结构，所以要进⾏调整；⼜由于删除元素的位置可能是任意的，所以调整过程⽐其它函数稍加繁琐。
public boolean remove(Object o) {
int i = indexOf(o); // 到数据对应的索引
if (i == -1) // 不存在的话返回false
return false;
else { // 存在的话调⽤removeAt⽅法，返回true
removeAt(i);
return true;
}
}
private E removeAt(int i) {
modCount++;
int s = --size; // 元素个数-1
if (s == i) // 如果是删除最后⼀个叶⼦节点
queue[i] = null; // 直接置空，删除即可，堆还是保持特质，不需要调整
else { // 如果是删除的不是最后⼀个叶⼦节点
E moved = (E) queue[s]; // 获得最后1个叶⼦节点元素
queue[s] = null; // 最后1个叶⼦节点置空
siftDown(i, moved); // 从上往下调整
if (queue[i] == moved) { // 如果从上往下调整完毕之后发现元素位置没变，从下往上调整
siftUp(i, moved); // 从下往上调整
if (queue[i] != moved)
return moved;
}
}
return null;
}
View Code
具体来说，remove(Object o)可以分为2种情况：
1. 删除的是最后⼀个元素。直接删除即可，不需要调整。
2. 删除的不是最后⼀个元素，从删除点开始以最后⼀个元素为参照调⽤siftDown()或siftUp()。
1. 删除的是最后⼀个元素。直接删除即可，不需要调整。
下⾯根据图解演⽰获取元素过程：
2. 删除的不是最后⼀个元素，从删除点开始以最后⼀个元素为参照调⽤siftDown()或siftUp()。
下⾯根据图解演⽰获取元素过程：
版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。
发表评论