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的都差不多，就不再赘述。