PriorityQueue源码分析

PriorityQueue源码分析来源:Java编程的逻辑1前导将新的头部与两个孩子节点中较小的比较,如果不大于该孩子节点,则满足堆的性质,结束,否则与较小的孩子进行交换,交换后,再与较小的孩子比较和交换,一直到没有孩子,或者不大于两个孩子节点。这个过程我们般称为siftdown与父节点比较,如果大于等于父节点,则满足堆的性质,结束,否则与父节点进行交换,然后再与父节点比较和交换,直到父节点为空或者大于等于父节点;称之为…

大家好,又见面了,我是你们的朋友全栈君。

来源:
Java编程的逻辑

1 前导

将新的头部与两个孩子节点中较小的比较,如果不大于该孩子节点,则满足堆的性质,结束,否则与较小的孩子进行交换,交换后,再与较小的孩子比较和交换,一直到没有孩子,或者不大于两个孩子节点。这个过程我们般称为siftdown

与父节点比较,如果大于等于父节点,则满足堆的性质,结束,否则与父节点进行交换,然后再与父节点比较和交换,直到父节点为空或者大于等于父节点;称之为siftup

2 实现原理

PriorityQueue是优先级队列,它首先实现了队列接口(Queue),与LinkedList类似,它的队列长度也没有限制,与一般队列的区别是,它有优先级的概念,每个元素都有优先级,队头的元素永远都是优先级最高的。

PriorityQueue内部是用堆实现的,内部元素不是完全有序的,不过,逐个出队会得到有序的输出。

虽然名字叫优先级队列,但也可以将PriorityQueue看做是一种比较通用的实现了堆的性质的数据结构,可以用PriorityQueue来解决适合用堆解决的问题

2.1 Queue接口

public interface Queue<E> extends Collection<E> { 
   
    boolean add(E e);
    boolean offer(E e);
    E remove();
    E poll();
    E element();
    E peek();
}

2.2 构造方法

public PriorityQueue() { 
   
    this(DEFAULT_INITIAL_CAPACITY, null);
}

public PriorityQueue(int initialCapacity) { 
   
    this(initialCapacity, null);
}

public PriorityQueue(int initialCapacity,Comparator<? super E> comparator) { 
   
    if (initialCapacity < 1)
        throw new IllegalArgumentException();
    this.queue = new Object[initialCapacity];
    this.comparator = comparator;
} 

PriorityQueue是用堆实现的,堆物理上就是数组,与ArrayList类似,PriorityQueue同样使用动态数组,根据元素个数动态扩展,initialCapacity表示初始的数组大小,可以通过参数传入。对于默认构造方法,initialCapacity使用默认值11。对于最后三个构造方法,它们接受一个已有的Collection,数组大小等于参数容器中的元素个数。

与TreeMap/TreeSet类似,为了保持一定顺序,PriorityQueue要求,要么元素实现Comparable接口,要么传递一个比较器Comparator

2.3 内部组成

private transient Object[] queue//实际存储元素的数组
private int size = 0;//当前元素个数
private final Comparator<? super E> comparator;
private transient int modCount = 0;

2.4 入队

public boolean offer(E e) { 
   
    if (e == null)
        throw new NullPointerException();
    modCount++;
    int i = size;
    if (i >= queue.length)
        grow(i + 1);//动态扩展
    size = i + 1;
    if (i == 0)
        queue[0] = e;
    else
        siftUp(i, e);//放入最后一个位置,向上调整
    return true;
}
//如果原长度比较小,扩展为2oldCapacity+2,否则就是增加50%,使用Arrays.copyOf方法拷贝数组
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));
    // newCapacity溢出时,就变为Integer.MAX_VALUE或MAX_ARRAY_SIZE
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    queue = Arrays.copyOf(queue, newCapacity);
}

private static int hugeCapacity(int minCapacity) { 
   
    if (minCapacity < 0) // overflow
        throw new OutOfMemoryError();
    return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE;
}
//新元素(x)不断与父节点(e)比较,如果新元素(x)大于等于父节点(e),则已满足堆的性质,退出循环,k就是新元素最终的位置;
//否则,将父节点往下移(queue[k]=e),继续向上寻找(k=parent)
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<? 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;
}

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

2.5 查看头部元素

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

2.6 删除头部元素

//返回结果result为第一个元素,x指向最后一个元素,将最后位置设置为null (queue[s] = null)
//最后调用siftDown将原来的最后元素x插入头部并调整堆
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;
}
//将原来的最后元素x插入头部并调整堆
private void siftDown(int k, E x) { 
   
    if (comparator != null)
        siftDownUsingComparator(k, x);
    else
        siftDownComparable(k, x);
}
//新元素key不断与较小的孩子比较,如果小于等于较小的孩子,则已满足堆的性质,退出循环,k就是最终位置;
//否则将较小的孩子往上移,继续向下寻找
private void siftDownComparable(int k, E x) { 
   
    Comparable<? super E> key = (Comparable<? super E>)x;
    int half = size >>> 1;        
    while (k < half) { 
   //编号为k的节点有孩子节点,则进入循环
        //表示较小的孩子编号,假定为左孩子,如果有右孩子(编号right)且小于左孩子则child会变为right
        int child = (k << 1) + 1; 
        Object c = queue[child];//较小的孩子节点
        int right = child + 1;
        if (right < size && ((Comparable<? super E>) c).compareTo((E) queue[right]) > 0)
            c = queue[child = right];//k=child这一步就不用判断,直接赋值为child即可
        if (key.compareTo((E) c) <= 0)
            break;
        queue[k] = c;//上移
        k = child;//从新的节点继续寻找
    }
    queue[k] = key;
}

private void siftDownUsingComparator(int k, E x) { 
   
    int half = size >>> 1;
    while (k < half) { 
   
        int child = (k << 1) + 1;
        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;
}

2.7 查找元素

public boolean contains(Object o) { 
   
    return indexOf(o) != -1;
}

private int indexOf(Object o) { 
   
    if (o != null) { 
   
        for (int i = 0; i < size; i++)
            if (o.equals(queue[i]))
                return i;
    }
    return -1;
}

2.8 根据值删除元素

//先查找元素的位置i,然后调用removeAt进行删除
public boolean remove(Object o) { 
   
    int i = indexOf(o);
    if (i == -1)
        return false;
    else { 
   
        removeAt(i);
        return true;
    }
}
//如果是删除最后一个位置,直接删即可;
//否则移动最后一个元素moved到位置i并进行堆调整;
//调整有两种情况,如果大于孩子节点,则向下调整,否则如果小于父节点则向上调整
private E removeAt(int i) { 
   
    assert i >= 0 && i < size;
    modCount++;
    int s = --size;
    if (s == i) //删除最后一个位置
        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;//则返回moved
        }
    }
    //其他情况返回null,即向下调整过,或没有调整过
    //用于正确实现PriorityQueue迭代器的删除方法
    return null;
}

2.9 构建初始堆

如果从一个既不是PriorityQueue也不是SortedSet的容器构造堆,代码为:

private void initFromCollection(Collection<? extends E> c) { 
   
    initElementsFromCollection(c);
    heapify();
}
//主要是初始化queue和size。
private void initElementsFromCollection(Collection<? extends E> c) { 
   
    Object[] a = c.toArray();
    if (a.getClass() != Object[].class)
        a = Arrays.copyOf(a, a.length, Object[].class);
    this.queue = a;
    this.size = a.length;
}
//从最后一个非叶子节点开始,一直往前直到根;
//对每个节点,执行向下调整siftdown;
//也就是说,自底向上,先使每个最小子树为堆,然后每对左右子树和其父节点合并,调整为更大的堆,因为每个子树已经为堆,所以调整就是对父节点执行siftdown,就这样一直合并调整直到根
private void heapify() { 
   
    for (int i = (size >>> 1) - 1; i >= 0; i--)
        siftDown(i, (E) queue[i]);
}

如果构造方法中的参数是PriorityQueue或SortedSet,则它们的toArray方法返回的数组就是有序的,就满足堆的性质,就不需要执行heapify了。

3 特点分析

PriorityQueue实现了Queue接口,有优先级,内部是用堆实现的,这决定了它有如下特点:

  • 实现了优先级队列,最先出队的总是优先级最高的,即排序中的第一个。
  • 优先级可以有相同的,内部元素不是完全有序的,如果遍历输出,除了第一个,其他没有特定顺序。
  • 查看头部元素的效率很高,为O(1),入队、出队效率比较高,为O(log2(N)),构建堆heapify的效率为O(N)。
  • 根据值查找和删除元素的效率比较低,为O(N)。
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/133616.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • JAVA常用框架及漏洞[通俗易懂]

    JAVA常用框架及漏洞[通俗易懂]三大语言常用框架及漏洞Java框架1.MyBatis是支持定制化SQL、存储过程以及高级映射的优秀的持久层框架,其主要就完成2件事情:封装JDBC操作 利用反射打通Java类与SQL语句之间的相互转换MyBatis的主要设计目的就是让我们对执行SQL语句时对输入输出的数据管理更加方便,所以方便地写出SQL和方便地获取SQL的执行结果才是MyBatis的核心竞争力。…

  • 盈通rx580游戏高手 bios_警告!盈通RX580 2048SP疑似采用二手显存颗粒

    盈通rx580游戏高手 bios_警告!盈通RX580 2048SP疑似采用二手显存颗粒今天我刷新闻,正好看到了超能网的一篇关于盈通RX5802048SP游戏高手OC的评测,但是看到显存颗粒的时候顿时起了疑心:链接:https://www.expreview.com/68378.html显存颗粒高清图:第一行编号:6EA47,按照美光颗粒打标定义6E代表16年第10周(美光官方定义,中文来自谷歌翻译)首先RX5802048SP是在18年下半年才出…

  • Oracle触发器trigger详解

    Oracle触发器trigger详解触发器相关概念及语法概述本篇博文中主要探讨以下内容:什么是触发器触发器的应用场景触发器的语法触发器的类型案例数据:触发器的概念和第一个触发器数据库触发器是一个与表相关联的,存储的PL/SQL语句。每当一个特定的数据操作语句(insertupdatedelete)在指定的表上发出时,Oracle自动执行触发器中定义的语句序列。举个简单的例子:当员…

  • 国外最流行的Bootstrap后台管理模板

    国外最流行的Bootstrap后台管理模板工欲善其事,必先利其器对于从事软件开发的您也一样,有一套熟悉的bootstrap后台ui框架让您的开发速度大幅度提升这是本人经常使用到的一些bootstrap后台框架推荐给大家第一名inspiniabootstrap演示地址http://cn.inspinia.cn效果图http://cn.inspinia.cnhttp://cn.inspinia.cn第二名…

  • html怎么隐藏播放器_css遮罩

    html怎么隐藏播放器_css遮罩<!DOCTYPEhtml><htmllang=”en”><head><metacharset=”UTF-8″><metaname=”viewport”content=”width=device-width,initial-scale=1.0″><metahttp-equiv=”X-UA-Compatible”content=”ie=edge”><title>视.

  • echarts地图文档_js下载本地文件

    echarts地图文档_js下载本地文件Echarts实现中国地图,含官方地图资源china.js

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号