PriorityQueue 源码解析 (四)

作者：知识浅谈

2022-10-18
吉林
本文字数：1522 字
阅读完需：约 1 分钟

🍁 作者：知识浅谈，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 的都差不多，就不再赘述。

发布于: 刚刚阅读数: 3

原文链接:【http://xie.infoq.cn/article/f5930f843f0bf57087ad53e99】。

知识浅谈

关注

公众号：知识浅谈 2022-06-22 加入

🍁 作者：知识浅谈，InfoQ签约作者，CSDN博客专家/签约讲师，华为云云享专家，阿里云签约博主，51CTO明日之星 📌 擅长领域：全栈工程师、爬虫、ACM算法 💒 公众号：知识浅谈 🔥 联系方式vx：zsqtcc

发布

暂无评论

创作场景

PriorityQueue 源码解析 (四)

🎈PriorityQueue 源码对应的函数

🍮boolean contains(Object o)

🍮Object[] toArray()

🍮final class Itr

🍮int size()

🍮void clear()

🍮E poll()

🍮siftUp(int k, E x)

🍮siftUpComparable 和 siftUpUsingComparator(int k, E x)

🍮 void siftDown(int k, E x)

🍮void heapify()

🍚总结

知识浅谈

评论