什么是java的优先队列 数据结构——优先队列

大家好，什么是java的优先队列相信很多的网友都不是很明白，包括数据结构——优先队列也是一样，不过没有关系，接下来就来为大家分享关于什么是java的优先队列和数据结构——优先队列的一些知识点，大家可以关注收藏，免得下次来找不到哦，下面我们开始吧！

数据结构——优先队列

优先队列顾名思义，就是优先权最大的排在队列的头部，而优先权的判断是根据对象的compare方法比较获取的，保证根节点的优先级一定比子节点的优先级大。所以放入到优先队列的元素要么实现了Comparable接口，要么在创造这个优先队列时，指定一个比较器。

普通的队列是一种先进先出的数据结构，元素在队列尾追加，而从队列头删除。在优先队列中，元素被赋予优先级。当访问元素时，具有最高优先级的元素最先删除。优先队列具有最高级先出（first in, largest out）的行为特征。通常采用堆数据结构来实现。

在Java中也实现了自己的优先队列 java.util.PriorityQueue，与我们自己写的不同之处在于，Java中内置的为最小堆，然后就是一些函数名不一样，底层还是维护了一个Object类型的数组，大家可以戳戳看有什么不同，另外如果想要把最小堆变成最大堆可以给PriorityQueue传入自己的比较器。

参考：

https://blog.csdn.net/love905661433/article/details/82989608

https://www.cnblogs.com/wmyskxz/p/9301021.html

java在存储数组时栈内存和堆内存的联系是什么

堆和栈都是一种数据项按序排列的数据结构。

（1）栈就像装数据的桶或箱子：它是一种具有后进先出性质的数据结构，也就是说后存放的先取，先存放的后取。这就如同要取出放在箱子里面底下的东西（放入的比较早的物体），首先要移开压在它上面的物体（放入的比较晚的物体）。

（2）堆像一棵倒过来的树：堆是一种经过排序的树形数据结构，每个结点都有一个值。通常所说的堆的数据结构，是指二叉堆。堆的特点是根结点的值最小（或最大），且根结点的两个子树也是一个堆。由于堆的这个特性，常用来实现优先队列，堆的存取是随意，这就如同在图书馆的书架上取书，虽然书的摆放是有顺序的，但是想取任意一本时不必像栈一样，先取出前面所有的书，书架这种机制不同于箱子，可以直接取出想要的书。

单调队列怎么用java实现

单调队列是一种严格单调的队列，可以单调递增，也可以单调递减。队首位置保存的是最优解，第二个位置保存的是次优解，ect。。。

单调队列可以有两个操作：

1、插入一个新的元素，该元素从队尾开始向队首进行搜索，找到合适的位置插入之，如果该位置原本有元素，则替换它。

2、在过程中从队首删除不符合当前要求的元素。

单调队列实现起来可简单，可复杂。简单的一个数组，一个head，一个tail指针就搞定。复杂的用双向链表实现。

用处：

1、保存最优解，次优解，ect。

2、利用单调队列对dp方程进行优化，可将O(n)复杂度降至O(1)。也就是说，将原本会超时的N维dp降优化至N-1维，以求通过。这也是我想记录的重点

是不是任何DP都可以利用单调队列进行优化呢？答案是否定的。

记住！只有形如 dp[i]=max/min(f[k])+ g[i]（k<i&& g[i]是与k无关的变量）才能用到单调队列进行优化。

优化的对象就是f[k]。

通过例题来加深感受

http://www.acm.uestc.edu.cn/problem.php?pid=1685

我要长高

Description

韩父有N个儿子，分别是韩一，韩二…韩N。由于韩家演技功底深厚，加上他们间的密切配合，演出获得了巨大成功，票房甚至高达2000万。舟子是名很有威望的公知，可是他表面上两袖清风实则内心阴暗，看到韩家红红火火，嫉妒心遂起，便发微薄调侃韩二们站成一列时身高参差不齐。由于舟子的影响力，随口一句便会造成韩家的巨大损失，具体亏损是这样计算的，韩一，韩二…韩N站成一排，损失即为C*（韩i与韩i+1的高度差（1<=i<N））之和，搞不好连女儿都赔了.韩父苦苦思索，决定给韩子们内增高（注意韩子们变矮是不科学的只能增高或什么也不做），增高1cm是很容易的，可是增高10cm花费就很大了，对任意韩i，增高Hcm的花费是H^2.请你帮助韩父让韩家损失最小。

Input

有若干组数据，一直处理到文件结束。每组数据第一行为两个整数：韩子数量N(1<=N<=50000)和舟子系数C(1<=C<=100)接下来N行分别是韩i的高度(1<=hi<=100)。

首先建立方程，很容易想到的是，dp[i][j]表示第 i个儿子身高为 j的最低花费。分析题目很容易知道，当前儿子的身高花费只由前一个儿子影响。因此，

dp[i][j]=min(dp[i-1][k]+ abs(j-k)*C+(x[i]-j)*(x[i]-j))；其中x[i]是第i个儿子原本的身高

我们分析一下复杂度。

首先有N个儿子，这需要一个循环。再者，每个儿子有0到100的身高，这也需要一维。再再者，0到100的每一个身高都可以有前一位儿子的身高0到100递推而来。

所以朴素算法的时间复杂度是O(n^3)。题目只给两秒，难以接受！

分析方程：

当第 i个儿子的身高比第 i-1个儿子的身高要高时，

dp[i][j]=min(dp[i-1][k]+ j*C-k*C+ X);( k<=j)其中 X=(x[i]-j)*(x[i]-j)。

当第 i个儿子的身高比第 i-1个儿子的身高要矮时，

dp[i][j]=min(dp[i-1][k]- j*C+k*C+ X);( k>=j)

对第一个个方程，我们令 f[i-1][k]=dp[i-1][k]-k*C, g[i][j]=j*C+X;于是 dp[i][j]= min(f[i-1][k])+ g[i][j]。转化成这样的形式，我们就可以用单调队列进行优化了。

第二个方程同理。

接下来便是如何实现，实现起来有点技巧。具体见下

View Code

还有一个比较适合理解该优化方法的题目是HDU 3401http://acm.hdu.edu.cn/showproblem.php?pid=3401

大概题目便是：一个人知道接下来T天的股市行情，想知道最终他能赚到多少钱。

构造状态dp[i][j]表示第i天拥有 j只股票的时候，赚了多少钱

状态转移有：

1、从前一天不买不卖:

dp[i][j]=max(dp[i-1][j],dp[i][j])

2、从前i-W-1天买进一些股:

dp[i][j]=max(dp[i-W-1][k]-(j-k)*AP[i],dp[i][j])

3、从i-W-1天卖掉一些股:

dp[i][j]=max(dp[i-W-1][k]+(k-j)*BP[i],dp[i][j])

这里需要解释一下为什么只考虑第i-W-1天的买入卖出情况即可。想想看，i-W-2天是不是可以通过不买不卖将自己的最优状态转移到第i-W-1天？以此类推，之前的都不需要考虑了，只考虑都i-W-1天的情况即可。

对买入股票的情况进行分析，转化成适合单调队列优化的方程形式

dp[i][j]=max(dp[i-W-1][k]+k*AP[i])-j*AP[i]。令f[i-W-1][k]=dp[i-W-1][k]+k*AP[i]，则dp[i][j]=max(f[i-W-1][k])- j*AP[i]。

这便可以用单调队列进行优化了。卖股的情况类似分析。

View Code

最后再说一个应用，用单调队列来优化多重背包问题 hdu 2191

如果有n个物品，每个物品的价格是w，重量是c，且每个物品的数量是k，那么用这样的一些物品去填满一个容量为m的背包，使得得到的背包价值最大化，这样的问题就是多重背包问题。

对于多重背包的问题，有一种优化的方法是使用二进制优化，这种优化的方法时间复杂度是O(m*∑log k[i])，具体可以见

http://www.cnblogs.com/ka200812/archive/2011/08/06/2129505.html

而利用单调队列的优化，复杂度是O(mn)

首先，对于第i件物品，如果已知体积为V，价值为W，数量为K，那么可以按照V的余数，将当前的体积J分成V组(0,1,....V-1)。

对于任意一组，可以得到转移方程：f[i*V+c]=f[k*V+c]+(i-k)*W，其中c是V组分组中的任意一个

令f[i*V+c]=dp[i]，那么就得到dp[i]=dp[k]+(i-k)*W(k>=i-K)

将dp[k]-k*W看做是优化函数，那么就可以运用单调队列来优化了

什么是java的优先队列和数据结构——优先队列的问题分享结束啦，以上的文章解决了您的问题吗？欢迎您下次再来哦！