JDK源码分析实战系列-PriorityQueue

本文主要是介绍JDK源码分析实战系列-PriorityQueue，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

PriorityQueue

Priority queue represented as a balanced binary heap: the two children of queue[n] are queue[2n+1] and queue[2(n+1)]

The element with the lowest value is in queue[0], assuming the queue is nonempty

优先级队列在JDK中有一个教科书式的示范实现，以上是JDK源码对实现的注释。和前面介绍的完全二叉树一样，存储元素时使用的父子节点在数组中的下标使用[2n+1] 和[2(n+1)]的公式计算，如果是反过来算父节点的下标位置公式是：(n-1）>>> 1。

PriorityQueue就是一个小顶堆的实现，也是被认为实现优先级队列最高效的方式。

下面就是对PriorityQueue的实现分析。

插入元素操作

插入元素的时候先判断了是否需要扩容，扩容在后面会提到，核心的逻辑是，元素先加到队尾，然后进行siftUp，使得新加入的元素调整成符合小顶堆的要求。

public boolean offer(E e) {
    if (e == null)
        throw new NullPointerException();
    modCount++;
    int i = size;
    if (i >= queue.length)
      	// 扩容
        grow(i + 1);
  	// 最后一个位置下标加1
    size = i + 1;
    if (i == 0)
      	// 第一个元素情况
        queue[0] = e;
    else
      	// 节点从尾部加入，然后上移操作，直到保持堆处于正确状态
        siftUp(i, e);
    return true;
}

PriorityQueue支持元素实现Comparable，也支持初始化时传入一个Comparator作为比较算子。所以siftUp区分了两种实现，都是差不多的，选一个分析一下，siftUp是调整堆的核心操作，这个操作是把元素从参数k位置开始，和父节点进行比较，如果比父节点小，就和父节点交换，不断重复，直到父节点比自己大或等于，或者自己已经移动到根节点才停止。

private void siftUp(int k, E x) {
    if (comparator != null)
        siftUpUsingComparator(k, x);
    else
        siftUpComparable(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改为父节点下标，下一轮循环从父节点开始
        k = parent;
    }
  	// 退出循环出来的，直接把值赋值给k下标即可
    queue[k] = key;
}

每增加一个元素，PriorityQueue就需要调整一次以确保小顶堆的排序，写操作是有一定消耗的。

结合siftUp方法实现

查询元素

查询操作其实就是遍历数组找出元素，不要感到惊讶，就是这么朴素无华，本质原因PriorityQueue的特性并不是快速定位某个元素的。是这里可能会有误解以为堆这种数据结构保证了左节点必然小于或大于右节点这样的规则，那么查找一个值可以是更有效率的二分法方式，而事实上堆并没有这个特性，所以查询一个元素就需要直接遍历全部元素。

标签：JDK,JDK源码,实战系列,PriorityQueue,元素,数据结构 来源：

本站声明： 1. iCode9 技术分享网（下文简称本站）提供的所有内容，仅供技术学习、探讨和分享； 2. 关于本站的所有留言、评论、转载及引用，纯属内容发起人的个人观点，与本站观点和立场无关； 3. 关于本站的所有言论和文字，纯属内容发起人的个人观点，与本站观点和立场无关； 4. 本站文章均是网友提供，不完全保证技术分享内容的完整性、准确性、时效性、风险性和版权归属；如您发现该文章侵犯了您的权益，可联系我们第一时间进行删除； 5. 本站为非盈利性的个人网站，所有内容不会用来进行牟利，也不会利用任何形式的广告来间接获益，纯粹是为了广大技术爱好者提供技术内容和技术思想的分享性交流网站。

这篇关于JDK源码分析实战系列-PriorityQueue的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！