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)


相关推荐

  • goland刷新时间永久激活破解方法

    goland刷新时间永久激活破解方法,https://javaforall.cn/100143.html。详细ieda激活码不妨到全栈程序员必看教程网一起来了解一下吧!

  • 物理讨论题复习

    物理讨论题复习请简要回答避雷针的工作原理?避雷针由于曲率半径小,电荷面密度大,从而产生尖端放电现象,导致自身与带电云层形成回路。导致自身电荷放出从而不会被雷击中,当带电云层密度过大,避雷针通过接地把电引下大地“分子电流假说“是谁提出的?请解释“分子电流”。安培。在原子、分子等物质微粒内部,存在着一种环形电流—-分子电流。分子电流使每个物质都成为微小的磁体,他的两侧相当于两个磁极请解释”磁偶极子“。磁偶极子是类比电偶极子而建立的物理模型。具有等值异号的两个点磁荷构成的系统称为磁偶极子。磁偶极子的物理

    2022年10月29日
  • HTTP Status 415 – Unsupported Media Type「建议收藏」

    HTTP Status 415 – Unsupported Media Type「建议收藏」HTTPStatus415–UnsupportedMediaType今天在测试springmvc的restful接口时候遇到了一个问题:通过body传参报错HTTPStatus415–UnsupportedMediaType简述restful接口传参方式restful推荐的传参方式:1.get/delete请求RequestParam,请求的url类似于http…

  • java 中getmapping,在Java spring尝试使用@getmapping到API时返回空JSON[通俗易懂]

    我有一个带有记录器的@bean,该记录器返回它从JIRAAPI获得的JSON数据。我当前正在记录启动程序时的响应。现在我想开始在我的控制器中使用@getmapping,并想在localhost:8080/上执行GET请求时记录信息。这是Controller类中的@bean,我想将其更改为@getmapping@BeanpublicCommandLineRunnerrun(RestTempla…

  • mysql如何修改root用户的密码「建议收藏」

    mysql如何修改root用户的密码「建议收藏」方法1:用SETPASSWORD命令首先登录MySQL。格式:mysql>setpasswordfor用户名@localhost=password(‘新密码’);例子:mysql>setpasswordforroot@localhost=password(‘123’);方法2:用mysqladmin格式:mysqladmin-u用户名-…

  • Jquery Ajax 跨域调用asmx类型 WebService范例

    Jquery Ajax 跨域调用asmx类型 WebService范例Ajax在Web2.0时代起着非常重要的作用,然而有时因为同源策略(SOP)(俗称:跨域问题(crossdomain))它的作用会受到限制。在本文中,将学习如何克服合作限制。本文以asmx方式搭建webservice作为测试用后端,给出完整的前后端调用解决方案、范例代码。

发表回复

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

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