专栏首页陈树义集合系列 Queue(九):PriorityQueue

集合系列 Queue(九):PriorityQueue

PriorityQueue 是一个优先级队列,其底层原理采用二叉堆实现。我们先来看看它的类声明:

public class PriorityQueue<E> extends AbstractQueue<E>
    implements java.io.Serializable

PriorityQueue 继承了 AbstractQueue 抽象类,具有队列的基本特性。

二叉堆

由于 PriorityQueue 底层采用二叉堆来实现,所以我们有必要先介绍下二叉堆。

二叉堆从结构上来看其实就是一个完全二叉树或者近似完全二叉树。二叉堆的每个左子树和右子树都是一个二叉堆。当父节点总是大于或等于一个子节点的键值时称其为「最大堆」,当父节点总是小于或等于任何一个子节点的键值时称其为「最小堆」。

        最小堆                               最大堆
             1                                11                          
         /        \                        /        \ 
       2           3                    9           10
    /     \      /     \             /     \      /     \ 
   4      5     6       7           5      6     7      8
  / \     / \                      / \     / \
 8  9 10 11                       1   2   3   4 

在二叉堆上常见的操作有:插入、删除,我们下面将详细介绍这两种操作。

插入

在二叉堆上插入节点的思路为:在数组的末尾插入新节点,然后不断上浮与父节点比较,直到找到合适的位置,使当前子树符合二叉堆的性质。二叉堆的插入操作最坏情况下需要从叶子上移到根节点,所以其时间复杂度为 O(logN)。

例如我们有下面这个最小堆,当我们插入一个值为 6 的节点,其调整过程如下:

        最小堆                              
             1                                                       
         /        \                       
       5           7                  
    /     \      /     \             
   8      10   48     55         
  / \     / \                     
 11 9   15                      
  • 在数组末尾插入新节点 6。
        最小堆                              
             1                                                       
         /        \                       
       5           7                  
    /     \      /     \             
   8      10   48     55         
  / \     / \                     
 11 9   15   6                   
  • 做上浮操作不断与父节点比较,直到其大于等于父节点。首先,6 < 10,所以交换位置。
        最小堆                              
             1                                                       
         /        \                       
       5           7                  
    /     \      /     \             
   8     → 6   48     55         
  / \     / \                     
 11 9   15   10                   
  • 继续与父节点比较,6 > 5 符合二叉树的性质,结束。

删除

二叉堆删除节点的思路为:

  1. 首先,如果删除的是末尾节点,那么直接删除即可,不需要调整。
  2. 接着,将删除节点与末尾节点交换数据,之后删除末尾节点,接着对删除节点不断做下沉操作。
  3. 最后,继续对删除节点做上浮操作。

例如我们有下面这个最小堆,当我们删除一个值为 7 的节点,其调整过程如下:

             1                                                       
         /        \                       
       5           7                  
    /     \      /     \             
   8      10   48     55         
  / \     / \   / \                   
 11 9   15  16 50 52                
  • 首先,将删除节点与末尾节点交换数据,并删除末尾节点。
             1                                                       
         /        \                       
       5           52                  
    /     \      /   \             
   8      10   48     55         
  / \     / \   / \                   
 11 9   15  16 50                      
  • 接着,对删除节点(52)不断做下沉操作。首先比较 52 与 48 和 55 的大小,将 52 与 48 交换。接着比较 52 与 50 的大小,将 52 与 50 交换。结果为:
             1                                                       
         /        \                       
       5           48                  
    /     \      /   \             
   8      10    50     55         
  / \     / \   / \                   
 11 9   15  16 52  
  • 最后,对删除节点(15)不断做上浮操作,结果为:
             1                                                       
         /        \                       
       5          15                  
    /     \      /     \             
   8      10   48     55         
  / \     / \                     
 11 9 

这里有一个细节,为什么做下沉操作之后,还需要做一次上浮操作呢?这是因为我们无法确定末尾节点的值与删除节点的父节点的大小关系。

在上面的例子中,我们删除的节点是 7,删除节点的父节点为1,末尾节点是 52。因为末尾节点和删除节点在同一个子树上,所以我们能够确定删除节点的父节点一定小于末尾节点,即 1 一定小于 52。所以我们不需要做上浮操作。

但是如果末尾节点与删除节点并不是在一颗子树上呢?此时我们无法判断末尾节点与删除节点父节点之间的大小关系,此时可能出现下面这种情况:

             1                                                       
         /        \                       
       5           230                  
    /     \      /   \             
   8      10   240     255         
  / \     / \   / \      / \           
 11 9   15  16 241 242 256 260 
/ \
27 33

此时如果我们删除 255 节点,那么删除节点的父节点为 230,末尾节点为 33。此时末尾节点就小于删除节点的父节点,需要做上浮操作。

原理

了解完二叉树的插入、删除原理,我们再来看看 PriorityQueue 的源码就很简单了。

类成员变量

// 队列数据
transient Object[] queue;  
// 大小
private int size = 0;
// 比较器
private final Comparator<? super E> comparator;

从类成员变量我们可以知道 PriorityQueue 底层采用数组存储数据,comparator 的实现决定了其实一个最大堆还是最小堆。默认情况下 PriorityQueue 是个最小堆。

构造方法

PriorityQueue 一共有 7 个构造方法。

public PriorityQueue() {
    this(DEFAULT_INITIAL_CAPACITY, null);
}
    
public PriorityQueue(int initialCapacity) {
    this(initialCapacity, null);
}
    
public PriorityQueue(Comparator<? super E> comparator) {
    this(DEFAULT_INITIAL_CAPACITY, comparator);
}
    
public PriorityQueue(int initialCapacity,
                     Comparator<? super E> comparator) { 
    if (initialCapacity < 1)
        throw new IllegalArgumentException();
    this.queue = new Object[initialCapacity];
    this.comparator = comparator;
}
// 传入集合初始值
public PriorityQueue(Collection<? extends E> c) {
    if (c instanceof SortedSet<?>) {
        SortedSet<? extends E> ss = (SortedSet<? extends E>) c;
        this.comparator = (Comparator<? super E>) ss.comparator();
        initElementsFromCollection(ss);
    }
    else if (c instanceof PriorityQueue<?>) {
        PriorityQueue<? extends E> pq = (PriorityQueue<? extends E>) c;
        this.comparator = (Comparator<? super E>) pq.comparator();
        initFromPriorityQueue(pq);
    }
    else {
        this.comparator = null;
        initFromCollection(c);
    }
}
// 传入PriorityQueue初始值
public PriorityQueue(PriorityQueue<? extends E> c) {
    this.comparator = (Comparator<? super E>) c.comparator();
    initFromPriorityQueue(c);
}
// 传入SortedSet初始值
public PriorityQueue(SortedSet<? extends E> c) {
    this.comparator = (Comparator<? super E>) c.comparator();
    initElementsFromCollection(c);
}

PriorityQueue 的构造方法比较多,但其功能都类似。如果传入的是普通集合,那么会将其数据复制,最后调用 heapify 方法进行二叉堆的初始化操作。但如果传入的数据是 SortedSet 或 PriorityQueue 这些已经有序的数据,那么就直接按照顺序复制数据即可。

核心方法

对于 PriorityQueue 来说,其核心方法有:获取、插入、删除、扩容。

获取

PriorityQueue 没有查询方法,取而代之的是获取数据的 peek 方法。

public E peek() {
    return (size == 0) ? null : (E) queue[0];
}

如果队列为空,那么返回 null 值,否则返回队列的第一个元素(即最大或最小值)。

插入

PriorityQueue 的数据插入过程,其实就是往二叉堆插入数据的过程。

public boolean add(E e) {
    return offer(e);
}
    
public boolean offer(E e) {
    if (e == null)
        throw new NullPointerException();
    modCount++;
    int i = size;
    // 1.容量不够,进行扩容
    if (i >= queue.length)
        grow(i + 1);
    size = i + 1;
    // 2.如果队列为空那么直接插入第一个节点
    // 否则插入末尾节点后进行上浮操作
    if (i == 0)
        queue[0] = e;
    else
        siftUp(i, e);
    return true;
}

private void siftUp(int k, E x) {
    if (comparator != null)
        siftUpUsingComparator(k, x);
    else
        // 3.采用默认的比较器
        siftUpComparable(k, x);
}
    
private void siftUpComparable(int k, E x) {
    Comparable<? super E> key = (Comparable<? super E>) x;
    while (k > 0) {
        // 4.将插入节点与父节点比较
        // 如果插入节点大于等于父节点,那么说明符合最小堆性质
        // 否则交换插入节点与父节点的值,一直到堆顶
        int parent = (k - 1) >>> 1;
        Object e = queue[parent];
        if (key.compareTo((E) e) >= 0)
            break;
        queue[k] = e;
        k = parent;
    }
    queue[k] = key;
}

插入的代码最终的逻辑是在 siftUpComparable 方法中,而该方法其实就是我们上面所说二叉堆插入逻辑的实现。

删除

PriorityQueue 的数据删除过程,其实就是将数据从二叉堆中删除的过程。

public boolean remove(Object o) {
    int i = indexOf(o);
    if (i == -1)
        return false;
    else {
        removeAt(i);
        return true;
    }
}
    
private E removeAt(int i) {
    // assert i >= 0 && i < size;
    modCount++;
    int s = --size;
    // 1.删除的是末尾节点,那么直接删除即可
    if (s == i) // removed last element
        queue[i] = null;
    else {
        E moved = (E) queue[s];
        queue[s] = null;
        // 2.对删除节点做下沉操作
        siftDown(i, moved);
        if (queue[i] == moved) {
            // 3.queue[i] == moved 表示删除节点根本没下沉
            // 意思是其就是该子树最小的节点
            // 这种情况下就需要进行上浮操作
            // 因为可能出现删除节点父节点大于删除节点的情况
            siftUp(i, moved);
            if (queue[i] != moved)
                return moved;
        }
    }
    return null;
}
    
private void siftDown(int k, E x) {
    if (comparator != null)
        siftDownUsingComparator(k, x);
    else
        siftDownComparable(k, x);
}
    
private void siftDownComparable(int k, E x) {
    Comparable<? super E> key = (Comparable<? super E>)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<? super E>) 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;
}

PriorityQueue 的删除操作需要注意的点是其下沉之后,还需要根据条件做一次上浮操作。关于为什么要做上浮操作,上面讲解二叉堆的时候已经提到了。

offer

因为 PriorityQueue 是队列,所以有 offer 操作。

对于 offer 操作来说,其实就是相当于往数组未插入数据,其逻辑细节我们在插入 add 方法中已经说到。

poll

因为 PriorityQueue 是队列,同样会有 poll 操作。而 poll 操作其实就是弹出队列头结点,相当于删除头结点。

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

之前我们说过删除节点的逻辑,即拿末尾节点值替代删除节点,然后做下沉操作。但是这里因为删除节点是根节点了,所以不需要做上浮操作。

扩容

当往队列插入数据时,如果队列容量不够则会进行扩容操作。

private void grow(int minCapacity) {
    int oldCapacity = queue.length;
    // Double size if small; else grow by 50%
    int newCapacity = oldCapacity + ((oldCapacity < 64) ?
                                     (oldCapacity + 2) :
                                     (oldCapacity >> 1));
    // overflow-conscious code
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    queue = Arrays.copyOf(queue, newCapacity);
}

PriorityQueue 的扩容非常简单。如果原来的容量小于 64,那么扩容为原来的两倍,否则扩容为原来的 1.5 倍。

总结

PriorityQueue 的实现是建立在二叉堆之上的,所以弄懂二叉堆就相当于弄懂了 PriorityQueue。PriorityQueue 默认情况下是最小堆,我们可以改变传入的比较器,使其成为最大堆。

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Java集合源码分析之LinkedList

    前面一篇我们分析了ArrayList的源码,这一篇分享的是LinkedList。我们都知道它的底层是由链表实现的,所以我们要明白什么是链表?

    须臾之余
  • Java常用问题排查工具

    jstack能得到运行java程序的java stack和native stack的信息

    王小明_HIT
  • Thinkphp命名规范

    公众号php_pachong
  • ThinkPHP调试方法

    一.调试模式 ThinkPHP 专门为开发过程而设置了调试模式,调试模式开启后,特别方便我们进行排 错和调整。但由于它执行效率会稍低,所以在正式部署项目的时候,...

    公众号php_pachong
  • Goroutine和Channel的的使用和一些坑以及案例分析

    阿伟
  • thinkphp自动加载机制

    PHP的自动加载机制个人感觉使用起来还是很方便的。关于PHP的自动加载机制,其核心的方法是__autoload()和spl_autoload_register(...

    公众号php_pachong
  • harris角点检测的简要总结

    harris角点检测是一种特征提取的方法,而特征提取正是计算机视觉的一种重要手段。尽管它看起来很复杂,其实也是基于数学原理和简单的图像处理来实现的。 本文之前...

    charlee44
  • 视图

    视图是 Web的可见内容,一般是 HTML结合 PHP 获取的数据提供给用户使用的部分,属于 MVC 中的 V。

    公众号php_pachong
  • PHP的自动加载机制[2]

    一、autoload机制概述 在使用PHP的OO模式开发系统时,通常大家习惯上将每个类的实现都存放在一个单独的文件里,这样会很容易实现对类进行复用,同时将来...

    公众号php_pachong
  • VC遍历访问目录下的文件

    访问目录文件夹下的文件是经常需要的操作,C/C++和win32接口都没有提供直接调用的函数。在这里总结了几个经常用到的函数,通过MFC的CFileFind函数递...

    charlee44

扫码关注云+社区

领取腾讯云代金券