JDK PriorityBlockingQueue remove(Object o) 源码分析

先知道PriorityBlockingQueue 是利用数组存储二叉堆实现。最小值(最优先)放在queue[0]位置。

//删除某个元素
public boolean remove(Object o) {
        final ReentrantLock lock = this.lock;
        lock.lock();
        try {
            int i = indexOf(o);//先找到元素的位置,见下面函数源码
            if (i == -1)
                return false;
            removeAt(i);//根据元素位置删除数据,见下面函数源码
            return true;
        } finally {
            lock.unlock();
        }
    }
//获取某个元素数组的下标
 private int indexOf(Object o) {
        if (o != null) {
            Object[] array = queue;
            int n = size;
            for (int i = 0; i < n; i++)
                if (o.equals(array[i]))
                    return i;
        }
        return -1;
    }

//根据下标去删除数据
  private void removeAt(int i) {
        Object[] array = queue;
        int n = size - 1;
        if (n == i) // removed last element
            array[i] = null;
        else {
            E moved = (E) array[n];//保存最后一个元素
            array[n] = null;//最后一个元素赋值null
            Comparator<? super E> cmp = comparator;
            if (cmp == null)
                siftDownComparable(i, moved, array, n);//以自实现Comparable接口对象为例(其实是把最后一个元素放到被删除元素的位置,让后通过,不断降级的算法,再构造合法的堆结构),见下面函数源码
            else
                siftDownUsingComparator(i, moved, array, n, cmp);
            if (array[i] == moved) {
                if (cmp == null)
                    siftUpComparable(i, moved, array);
                else
                    siftUpUsingComparator(i, moved, array, cmp);
            }
        }
        size = n;
    }


    /**
     * Inserts item x at position k, maintaining heap invariant by
     * demoting x down the tree repeatedly until it is less than or
     * equal to its children or is a leaf.
     *  把x 元素放在 下标k的位置。通过循环降级x的位置(如果有必要),直到保证x小于等于它的任何子节点,以维持堆的结构合法性。
     * @param k the position to fill
     * @param x the item to insert
     * @param array the heap array
     * @param n heap size
     */
    private static <T> void siftDownComparable(int k, T x, Object[] array,
                                               int n) {
        if (n > 0) {
            Comparable<? super T> key = (Comparable<? super T>)x;
            int half = n >>> 1;           // loop while a non-leaf 当是非叶子节点位置,才循环。 
            while (k < half) {//这个意思就是,如果k位置有子节点,那么k的位置一定在数组前半部分。因为在数组中,一个元素位置为k那么它的左节点在2k+1位置,右节点在2k+2位置。
                int child = (k << 1) + 1; // assume left child is least
                Object c = array[child];
                int right = child + 1;//右孩子下标
                if (right < n &&
                    ((Comparable<? super T>) c).compareTo((T) array[right]) > 0)//如果右孩子小于左孩子
                    c = array[child = right];//获取右孩子
		//上面语句其实是选择左右孩子较小的一个(值和位置),写法我学习了!!
                if (key.compareTo((T) c) <= 0)//如果插入值比左孩子/右孩子(较小的一个)小,就是符合二叉堆,结束循环,
                    break;
                array[k] = c;//把左孩子/右孩子(较小的一个)赋值到k位置
                k = child;//把左孩子/右孩子(较小的一个)的位置赋值给k,找他们的左右孩子,下轮循环。
            }
            array[k] = key;//赋值插入值到k位置
        }
    }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏开发之途

Java集合框架源码解析之LinkedHashMap

13430
来自专栏大闲人柴毛毛

图的遍历(BFS+DFS)

图的遍历与树的遍历基本类似,但要注意两个不同: 1. 图中可能有环路,因此可能会导致死循环; 2. 一个图可能由多个独立的子图构成,因此一条路径走到头...

470110
来自专栏于晓飞的专栏

读 Java Arrays 源码 笔记

Arrays.java是Java中用来操作数组的类。使用这个工具类可以减少平常很多的工作量。了解其实现,可以避免一些错误的用法。

11120
来自专栏用户画像

剑指offer 包含min函数的栈

定义栈的数据结构,请在该类型中实现一个能够得到栈中所含最小元素的min函数(时间复杂度应为O(1))。

9820
来自专栏好好学java的技术栈

“365算法每日学计划”:04打卡-自己动手写一个单链表

15730
来自专栏Jack的Android之旅

疯狂Java笔记之常见java集合的实现细节

首先Set是一种集合元素无序,不可重复的集合。而Map则代表一种有多个key-value对组成的集合,Map集合类似于传统的关联数据。看起来他们没哟什么关联,实...

7020
来自专栏Java帮帮-微信公众号-技术文章全总结

Java集合详解【面试+工作】

在说集合前我们不得不说一下数组 数组的作用: 存放一组相同的数据类型(基本或对象)的数据,从而实现对数据的管理 优势:可以快速的通过下标对数组元素进行访问,效率...

45960
来自专栏mukekeheart的iOS之旅

Java基础——集合框架

  Java的集合框架是Java中很重要的一环,Java平台提供了一个全新的集合框架。“集合框架”主要由一组用来操作对象的接口组成。不同接口描述一组不同数据类型...

28860
来自专栏开发之途

Java集合框架源码解析之LinkedList

13630
来自专栏好好学java的技术栈

自己动手写一个单链表

单向链表(单链表)是链表的一种,其特点是链表的链接方向是单向的,对链表的访问要通过顺序读取从头部开始。

29860

扫码关注云+社区

领取腾讯云代金券