PriorityQueue

定义优先级队列,实现了AbstractQueue

优先队列跟普通的队列不一样,普通队列是一种遵循FIFO规则的队列,拿数据的时候按照加入队列的顺序拿取。 而优先队列无论插入的顺序如何每次拿数据的时候都会拿出优先级最高(优先级value最小)的数据。

Priority原理分析

优先队列内部维护着一个堆,每次取数据的时候都从堆顶拿数据,这就是优先队列的原理。

每次add的时候都会siftUp(i, e);从下往上调整,因为新增元素是加到最后一个叶子节点

每次poll的时候都会siftDown(0, x); 从上往下调整,因为删除元素是删除堆顶的元素

例子:

Comparatortest = new Comparator() { 

 @Override 

 public int compare(Integer t1, Integer t2) { return t1 - t2;} }; 

 PriorityQueue test2 = new PriorityQueue(6, test);

    test2.add(6);

    test2.add(10);

    test2.add(2);

    test2.add(3);

    test2.add(4);

    test2.add(5);

    System.out.println(test2.toString());

    System.out.println(test2.remove());

输出:

[10, 6, 5, 3, 4, 2]

2

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
【社区内容提示】社区部分内容疑似由AI辅助生成,浏览时请结合常识与多方信息审慎甄别。
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

相关阅读更多精彩内容

友情链接更多精彩内容