资讯专栏INFORMATION COLUMN

【java源码一带一路系列】之PriorityQueue

AlphaWallet / 593人阅读

摘要:满二叉树所有的节点都有个叶子节点,除了最后层叶子节点节点数和深度的关系第层上的节点数为第个节点的父节点左子节点右子节点参考下图完全二叉树有且仅有最底层叶子节点不完整就是完全二叉树。例如把去掉最小堆父节点小于左右子节点的完全二叉树。

按照下图的配方,走了一遍源码。
凑齐PriorityQueue就可以召唤神龙了。
Ler"s go go go!


结构
/**
 * Priority queue represented as a balanced binary heap: the two
 * children of queue[n] are queue[2*n+1] and queue[2*(n+1)].  The
 * priority queue is ordered by comparator, or by the elements"
 * natural ordering, if comparator is null: For each node n in the
 * heap and each descendant d of n, n <= d.  The element with the
 * lowest value is in queue[0], assuming the queue is nonempty.
 */
transient Object[] queue; // non-private to simplify nested class access

没错这是个数组,为了更好的理解注释的含义,请看下面↓。

满二叉树:

所有的节点都有2个叶子节点,除了最后层叶子节点;

节点数n和深度d的关系 n=2^d-1;

第i层上的节点数为2^(i-1);

第n个节点的父节点:n/2,左子节点:2n,右子节点:2n+1;(参考下图)

完全二叉树:

有且仅有最底层叶子节点不完整就是完全二叉树。(例如:把15去掉)

最小堆:

父节点小于左右子节点的完全二叉树。

转数组:

用数组来存储二叉树后(参见下图)可得,根节点A[0];左子节点a[2n+1];右子节点a[2(n+1)],父节点a[(n-1)/2]。(n为数组下标,从0开始)

是的,优先队列的存储结构大概就是这样推演而来。

heapify() --> siftDown() --> siftDownComparable() --> siftDownUsingComparator()
/**
 * Establishes the heap invariant (described above) in the entire tree,
 * assuming nothing about the order of the elements prior to the call.
 */
@SuppressWarnings("unchecked")
private void heapify() {
    for (int i = (size >>> 1) - 1; i >= 0; i--)
        siftDown(i, (E) queue[i]);
}

/**
 * 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.
 *
 * @param k the position to fill
 * @param x the item to insert
 */
private void siftDown(int k, E x) {
    if (comparator != null)
        siftDownUsingComparator(k, x);
    else
        siftDownComparable(k, x);
}

@SuppressWarnings("unchecked")
private void siftDownComparable(int k, E x) {
    Comparable key = (Comparable)x;
    int half = size >>> 1;        // loop while a non-leaf
    while (k < half) {
        int child = (k << 1) + 1; // assume left child is least
        Object c = queue[child];
        int right = child + 1;
        if (right < size &&
            ((Comparable) c).compareTo((E) queue[right]) > 0)
            c = queue[child = right];
        if (key.compareTo((E) c) <= 0)
            break;
        queue[k] = c;
        k = child;
    }
    queue[k] = key;
}

@SuppressWarnings("unchecked")
private void siftDownUsingComparator(int k, E x) {
    int half = size >>> 1;
    while (k < half) {
        int child = (k << 1) + 1; //2n + 1,这里n是下标
        Object c = queue[child];
        int right = child + 1;
        if (right < size &&
            comparator.compare((E) c, (E) queue[right]) > 0) // 找出最小子节点
            c = queue[child = right];
        if (comparator.compare(x, (E) c) <= 0) // 父节点小则退出循环,否则进行替换
            break;
        queue[k] = c;
        k = child;
    }
    queue[k] = x;
}

这是任意数组最小堆化的过程。如果是一个合格的最小堆,那么所有的父节点都在数组前半部分,而通过父节点又能得到左右子节点。因此源码一上来就“size >>> 1”(相当于除以2),只需对前半部分进行循环处理,使得循环结束后所有父节点均大于左/右子节点。这里非根父节点会被多次比较到。heapify()后将得到上文所说的最小堆数组。

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

poll()的核心也是siftDown,而这里的“siftDown(0, x);”与之前的“siftDown(i, (E) queue[i]);”不同的是,下标0所对应的元素本非x。也就是说,这里进行了个转换:把最后queue[s]替换了queue[0]进行新的最小堆数组化。

 /**
 * Removes a single instance of the specified element from this queue,
 * if it is present.  More formally, removes an element {@code e} such
 * that {@code o.equals(e)}, if this queue contains one or more such
 * elements.  Returns {@code true} if and only if this queue contained
 * the specified element (or equivalently, if this queue changed as a
 * result of the call).
 *
 * @param o element to be removed from this queue, if present
 * @return {@code true} if this queue changed as a result of the call
 */
public boolean remove(Object o) {
    int i = indexOf(o);
    if (i == -1)
        return false;
    else {
        removeAt(i);
        return true;
    }
}

/**
 * Removes the ith element from queue.
 *
 * Normally this method leaves the elements at up to i-1,
 * inclusive, untouched.  Under these circumstances, it returns
 * null.  Occasionally, in order to maintain the heap invariant,
 * it must swap a later element of the list with one earlier than
 * i.  Under these circumstances, this method returns the element
 * that was previously at the end of the list and is now at some
 * position before i. This fact is used by iterator.remove so as to
 * avoid missing traversing elements.
 */
@SuppressWarnings("unchecked")
private E removeAt(int i) {
    // assert i >= 0 && i < size;
    modCount++;
    int s = --size;
    if (s == i) // removed last element
        queue[i] = null;
    else {
        E moved = (E) queue[s];
        queue[s] = null;
        siftDown(i, moved); 
        if (queue[i] == moved) {
            siftUp(i, moved);
            if (queue[i] != moved)
                return moved;
        }
    }
    return null;
}

如你所见,remove()也用到了siftDown()(同时还有siftUp(),下面介绍)。这里 经过siftDown后,如果queue[i] == moved则表示queue[i]的左右子节点都大于moved,即保证了i节点子树是最小堆,但queue[i]的父节点是否小于moved却未知,故又进行了siftUp。(图片来自【2】)

/**
 * Inserts item x at position k, maintaining heap invariant by
 * promoting x up the tree until it is greater than or equal to
 * its parent, or is the root.
 *
 * To simplify and speed up coercions and comparisons. the
 * Comparable and Comparator versions are separated into different
 * methods that are otherwise identical. (Similarly for siftDown.)
 *
 * @param k the position to fill
 * @param x the item to insert
 */
private void siftUp(int k, E x) {
    if (comparator != null)
        siftUpUsingComparator(k, x);
    else
        siftUpComparable(k, x);
}
    
@SuppressWarnings("unchecked")
private void siftUpComparable(int k, E x) {
    Comparable key = (Comparable) 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;
}

@SuppressWarnings("unchecked")
private void siftUpUsingComparator(int k, E x) {
    while (k > 0) {
        int parent = (k - 1) >>> 1;
        Object e = queue[parent];
        if (comparator.compare(x, (E) e) >= 0)
            break;
        queue[k] = e;
        k = parent;
    }
    queue[k] = x;
}

与之相对的,还有名为siftUpComparable()/siftUpUsingComparator()的方法。在新增元素时被调用。新增元素放在下标为size的位置。这里的down与up指的是被比较对象x的去向。比较后x被赋值给子节点就是down,被赋值给父节点就是up。当然你来写的时候也可能新增时,从上到下循环遍历。

说点什么

PriorityQueue有序;不允许为null;非线程安全;(PriorityBlockingQueue线程安全);没有介绍的地方大抵与其他集合框架相似,如扩容机制等。

优先队列每次出队的元素都是优先级最高(权值最小)的元素,通过比较(Comparator或元素本身自然排序)决定优先级。

记得常来复习啊~~~

更多有意思的内容,欢迎访问笔者小站: rebey.cn

推荐文章:

【1】【深入理解Java集合框架】深入理解Java PriorityQueue;

【2】java集合——Queue;

文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。

转载请注明本文地址:https://www.ucloud.cn/yun/67212.html

相关文章

  • java源码一带一路系列LinkedHashMap.afterNodeAccess()

    摘要:如今行至于此,当观赏一方。由于所返回的无执行意义。源码阅读总体门槛相对而言比,毕竟大多数底层都由实现了。比心可通过这篇文章理解创建一个实例过程图工作原理往期线路回顾源码一带一路系列之源码一带一路系列之源码一带一路系列之 本文以jdk1.8中LinkedHashMap.afterNodeAccess()方法为切入点,分析其中难理解、有价值的源码片段(类似源码查看是ctrl+鼠标左键的过程...

    levy9527 评论0 收藏0
  • java源码一带一路系列ArrayList

    摘要:一路至此,风景过半。与虽然名字各异,源码实现基本相同,除了增加了线程安全。同时注意溢出情况处理。同时增加了考虑并发问题。此外,源码中出现了大量泛型如。允许为非线程安全有序。 一路至此,风景过半。ArrayList与Vector虽然名字各异,源码实现基本相同,除了Vector增加了线程安全。所以作者建议我们在不需要线程安全的情况下尽量使用ArrayList。下面看看在ArrayList源...

    RebeccaZhong 评论0 收藏0
  • java源码一带一路系列HashSet、LinkedHashSet、TreeSet

    摘要:同样在源码的与分别见看到老朋友和。这样做可以降低性能消耗的同时,还可以减少序列化字节流的大小,从而减少网络开销框架中。使用了反射来寻找是否声明了这两个方法。十进制和,通过返回值能反应当前状态。 Map篇暂告段落,却并非离我们而去。这不在本篇中你就能经常见到她。HashSet、LinkedHashSet、TreeSet各自基于对应Map实现,各自源码内容较少,因此归纳为一篇。 HashS...

    UCloud 评论0 收藏0
  • java源码一带一路系列HashMap.compute()

    摘要:本篇涉及少许以下简称新特性,请驴友们系好安全带,准备开车。观光线路图是在中新增的一个方法,相对而言较为陌生。其作用是把的计算结果关联到上即返回值作为新。实际上,乃缩写,即二元函数之意类似。 本文以jdk1.8中HashMap.compute()方法为切入点,分析其中难理解、有价值的源码片段(类似源码查看是ctrl+鼠标左键的过程)。本篇涉及少许Java8(以下简称J8)新特性,请驴友们...

    wapeyang 评论0 收藏0
  • java源码一带一路系列HashMap.putAll()

    摘要:观光线路图将涉及到的源码全局变量哈希表初始化长度默认值是负载因子默认表示的填满程度。根据是否为零将原链表拆分成个链表,一部分仍保留在原链表中不需要移动,一部分移动到原索引的新链表中。 前言 本文以jdk1.8中HashMap.putAll()方法为切入点,分析其中难理解、有价值的源码片段(类似ctrl+鼠标左键查看的源码过程)。✈观光线路图:putAll() --> putMapEnt...

    chanjarster 评论0 收藏0

发表评论

0条评论

最新活动
阅读需要支付1元查看
<