「java优先级队列」java优先级队列为什么是小顶堆
今天给各位分享java优先级队列的知识，其中也会对java优先级队列为什么是小顶堆进行解释，如果能碰巧解决你现在面临的问题，别忘了关注本站，现在开始吧！
本文目录一览：
java优先队列这里的构造函数用法该怎么理解？
很明显，用到的构造函数是 PriorityQueue(Comparator? super E comparator) 。
所以 ((a, b) - a[0] - b[0]) 所代表的是一个 comparator 。
不明白这个式子，说明对与 JDK8 中的 lamda 表达式不熟悉 。
其实这个式子是 对 Comparator 接口中 int compare(T o1, T o2)方法的具体实现 。
(a, b) 代表的是 compare方法中的两个参数。
a[0] - b[0] 代表compare方法的返回值。
PriorityQueue 有了 comparator 比较器，便能确定队列中元素的优先级。
面试官再问你优先级队列，请把这篇文章丢给他
假如你设计的事件系统中有很多的事件，每个事件都定义了不同的权重值，系统需要优先处理权重较高的事件，这里你就需要使用到优先级队列，本篇我们一起来学习实现优先级队列的常用方式
在实现之前，首先我们需要先定义出优先级队的API，优先级队列是一种抽象的数据结构，我们依然可以基于前面我们使用到的队列API来修改；需要了解之前的队列的实现可以查看《面试的季节到了，老哥确定不来复习下数据结构吗》
其中的入队列 enqueue 和出队列 dequeue 是我们主要需要实现的方式，也是优先级队列的核心方法
实现优先级队列的最简单实现可以参考《面试的季节到了，老哥确定不来复习下数据结构吗》中栈的实现方式， enqueue 和栈的 push 方式实现方式一致， dequeue 可以参考选择排序的实现，循环一遍数组，找出最大值和数组最后一个元素交换，然后删除它；
这里只实现了定长的优先级队列，如何实现自动扩容呢？也可以参考这篇文章《面试的季节到了，老哥确定不来复习下数据结构吗》；基于无序数组实现的enqueue时间复杂度是O(1)，dequeue时间复杂度是O(n)
基于有序数组实现就是在入队的时候保证数组有序，那么在出队列的时候可以直接删掉最大值；插入的过程和插入排序类似的操作
enqueue时间复杂度是O(n)，dequeue时间复杂度是O(1)
基于链表的实现与上面的类似，有兴趣的可以自己实现
在二叉堆中，每个节点都将大于等于它的子节点，也成为堆有序；其中根节点是最大的节点。
二叉堆的表示：
重点：
在一个二叉堆中，位置k节点的父节点的位置为 k/2 ,它的两个子节点的位置为 2k 和 2k+1 ; 基于这点，我们可以用数组来表示二叉堆，通过移动数组的下标来找到节点父节点和子节点
在元素进行插入和删除操作的过程中，会破坏堆有序，所以我们需要做一些操作来保证堆再次有序；主要有两种情况，当某个节点的优先级上升，我们需要 由下向上恢复堆有序（下沉） ；当某个节点优先级下降，我们需要 由上向下恢复堆有序（上浮）
根据当前的节点k找到父节点的位置k/2，比较当前节点和父节点，如果比父节点大就交换，直到找个比当前节点大的父节点或者已上浮到了根节点
文中所有源码已放入到了github仓库
文中或许会存在或多或少的不足、错误之处，有建议或者意见也非常欢迎大家在评论交流。
最后， 写作不易，请不要白嫖我哟 ，希望朋友们可以 点赞评论关注 三连，因为这些就是我分享的全部动力来源🙏
java,优先级队列和有序数组区别？
数组是有序的，访问和修改都要按下标一个个地去找。
优先级队列，是要看优先级的，谁的优先级更高，谁就先得到权限。不分排队的顺序。
java优先级队列的介绍就聊到这里吧，感谢你花时间阅读本站内容，更多关于java优先级队列为什么是小顶堆、java优先级队列的信息别忘了在本站进行查找喔。