Java Collection - PriorityQueue 优先队列
2021-09-28 18:15
标签：仿函数 顺序 off title ring 删除 rem 节点 blank 总结 优先队列的作用是能保证每次取出的元素都是队列中权值最小的（Java的优先队列每次取最小元素，C++的优先队列每次取最大元素）。这里牵涉到了大小关系，元素大小的评判可以通过元素本身的自然顺序（natural ordering），也可以通过构造时传入的比较器（Comparator，类似于C++的仿函数）。 Java中PriorityQueue实现了Queue接口，不允许放入null元素；其通过堆实现，具体说是通过完全二叉树（complete binary tree）实现的小顶堆（任意一个非叶子节点的权值，都不大于其左右子节点的权值）。 Java中使用数组的形式保存小顶堆的结构。父节点和子节点的编号是有联系的，更确切的说父子节点的编号之间有如下关系： leftNo = parentNo*2+1 rightNo = parentNo*2+2 parentNo = (nodeNo-1)/2 PriorityQueue解析 详细内容 PriorityQueue 继承关系 add() & offer() 源码 -- add(E e)和offer(E e)的语义相同，都是向优先队列中插入元素，只是Queue接口规定二者对插入失败时的处理不同，前者在插入失败时抛出异常，后则则会返回false。对于PriorityQueue这两个方法其实没什么差别。 peek() 源码 remove() & poll() 源码 -- remove()和poll()方法的语义也完全相同，都是获取并删除队首元素，区别是当方法失败时前者抛出异常，后者返回null。由于删除操作会改变队列的结构，为维护小顶堆的性质，需要进行必要的调整。 参考链接 PriorityQueue 原理与应用 深入理解Java PriorityQueue Java Collection - PriorityQueue 优先队列标签：仿函数 顺序 off title ring 删除 rem 节点 blank 原文地址：https://www.cnblogs.com/frankcui/p/12088422.html
文章标题：Java Collection - PriorityQueue 优先队列
文章链接：http://soscw.com/essay/108195.html