PriorityQueue 源码解析(四)

???? 作者：知识浅谈，CSDN博客专家，阿里云签约博主，InfoQ签约博主，华为云云享专家

???? 擅长领域：全栈工程师、爬虫、ACM算法

???? 公众号：知识浅谈

PriorityQueue 源码解析(四)总结

正菜来了⛳⛳⛳

????PriorityQueue 源码对应的函数

????boolean contains(Object o)

含义：这个函数的意思是查看优先队列中是否含有o这个元素，方法里边调用的还是indexOf这个函数。

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

????Object[] toArray()

含义：返回一个包含此队列中所有元素的数组。元素没有特定的顺序，里边调用了Arrays.copyOf函数把优先对列中的数组克隆一个新数组出来。

public Object[] toArray() {
return Arrays.copyOf(queue, size);
}

????final class Itr

含义：静态内部类Itr，主要是用于实现迭代的使用，具体的内部的内容可以自行查看。

private final class Itr implements Iterator<E> {
}

????int size()

含义：因为优先队列类中的size代表的是队列中的元素个数，所以调用size（）函数会返回当前优先队列中的元素个数。

public int size() {
return size;
}

????void clear()

含义：这个clear的含义就是把queue[i]的指向都变为空，并把size变为0；

public void clear() {
modCount++;
for (int i = 0; i < size; i++)
queue[i] = null;
size = 0;
}

????E poll()

含义：这个poll函数的意思是取出队列头部的元素并且把这个元素从队列中删除。

@SuppressWarnings("unchecked")
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;
}

????siftUp(int k, E x)

含义：这个函数的意思是在位置 k 处插入项 x，通过将 x 提升到树上直到它大于或等于其父项或者是根来保持堆不变。简化和加速强制和比较。 Comparable 和 Comparator 版本被分成不同的方法，这些方法在其他方面是相同的。（对于 siftDown 也是如此。）

private void siftUp(int k, E x) {
if (comparator != null)
siftUpUsingComparator(k, x);
else
siftUpComparable(k, x);
}

上边的而函数调用了siftUpUsingComparator和siftUpComparable，我们接着看着两个函数。

????siftUpComparable和siftUpUsingComparator(int k, E x)

含义：这个函数的意思是从k这个位置开始找到适合x的位置然后插入。

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

???? void siftDown(int k, E x)

含义：在位置 k 处插入项 x，通过重复将 x 降级到树下直到它小于或等于其子项或者是叶子来保持堆不变。

private void siftDown(int k, E x) {
if (comparator != null)
siftDownUsingComparator(k, x);
else
siftDownComparable(k, x);
}

上边函数中调用的siftDownUsingComparator和siftDownComparable几乎是一样的。

????void heapify()

含义：在整个树中建立堆不变量（如上所述），不假设调用之前元素的顺序。

private void heapify() {
for (int i = (size >>> 1) - 1; i >= 0; i--)
siftDown(i, (E) queue[i]);
}

????总结

以上是关于优先队列的源码，当然里边还有像是writeObject和readObject这种对象序列化和反序列化方法和之前的ArraylIst的都差不多，就不再赘述。

秒客网