Java优先队列是怎样的，很多新手对此不是很清楚，为了帮助大家解决这个难题，下面小编将为大家详细讲解，有这方面需求的人可以来学习下，希望你能有所收获。
优先队列（priority queue）是一种特殊的数据结构。
队列中每一个元素都被分配到一个优先权值，出队顺序按照优先权值来划分。
一般有两种出队顺序：高优先权出队或低优先权出队。priority queue至少要有两个最基本的ADT：进队，出队（按照高优先权或低优先权）
产生原因：同样是为了提高数据处理的效率。试想，要实现优先队列对应的功能，若使用链表或者数组，那么要么先排序再插入，要么先插入再查找最大最小元素。这样一来，入队出队的时间复杂度至少为O(N)。
优先队列出队和入队的时间复杂度均为O(log N)。
优先队列基于二叉堆实现。
堆是一种特殊的二叉树，性质如下：
每个结点的值都大于或等于其左右孩子结点的值（大顶堆），或每个结点的值都小宇或等于其左右孩子的值（小顶堆）。
必须满足完全二叉树的结构。
完全二叉树 complete binary tree
叶节点只可能出现在最后两层，且最后一层的叶节点都左对齐
一棵深度为h的完全二叉树
满二叉树 full binary tree
深度为h的满二叉树有（2^h）-1个结点
由二叉堆的定义可以看出，跟结点一定是二叉堆中结点值最大（或最小）的。较大（或较小）的结点靠近根节点
堆的存储结构：
一般情况下，堆用数组来存储，第i个结点的父节点的下标就是（i-1）/2.
如果用层序遍历顺序将大顶堆和小顶堆存入数组，
则关系如图：
插入：插入一个元素之后，新元素首先被插入表层（即最后一层尽可能左边的位置），之后再根据堆的性质进行调整。
例：写出一次一个地将10,12,1,14,6,5,8,15,3,9,7,4,11,13和2插入一个初始为空的二叉堆的结果
删除：删除总是发生在根处，之后将最后一个元素（即最后一层最右边的元素）拿来填补空缺，之后根据堆的性质进行调整堆的结构。
看完上述内容是否对您有帮助呢？如果还想对相关知识有进一步的了解或阅读更多相关文章，请关注亿速云行业资讯频道，感谢您对亿速云的支持。
免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：is@yisu.com进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。
