锐客网

  1. 首页 > 睿知 > it技术 > >

java实现优先队列代码 java实现优先队列代码怎么写

IT技术队列

单调队列怎么用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]（kig[i]是与k无关的变量）才能用到单调队列进行优化 。
优化的对象就是f[k] 。
通过例题来加深感受
我要长高
Description
韩父有N个儿子，分别是韩一，韩二…韩N 。由于韩家演技功底深厚，加上他们间的密切配合，演出获得了巨大成功，票房甚至高达2000万 。舟子是名很有威望的公知，可是他表面上两袖清风实则内心阴暗，看到韩家红红火火，嫉妒心遂起，便发微薄调侃韩二们站成一列时身高参差不齐 。由于舟子的影响力，随口一句便会造成韩家的巨大损失，具体亏损是这样计算的，韩一，韩二…韩N站成一排，损失即为C*（韩i与韩i 1的高度差（1=iN））之和，搞不好连女儿都赔了.韩父苦苦思索 ， 决定给韩子们内增高（注意韩子们变矮是不科学的只能增高或什么也不做），增高1cm是很容易的，可是增高10cm花费就很大了，对任意韩i ， 增高Hcm的花费是H^2.请你帮助韩父让韩家损失最小 。
Input
【java实现优先队列代码 java实现优先队列代码怎么写】有若干组数据 ， 一直处理到文件结束 。每组数据第一行为两个整数：韩子数量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*CX);( k=j ) 其中 X=(x[i]-j)*(x[i]-j) 。
当第 i 个儿子的身高比第 i-1 个儿子的身高要矮时 ，
dp[i][j]=min(dp[i-1][k] - j*C k*CX);( 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 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])，具体可以见
而利用单调队列的优化 ， 复杂度是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中关于堆实现优先队列的问题，我编译可以通过，但是运行的时候会出现数组越界的错误，是怎么回事？看下MaxHeapify这个方法java实现优先队列代码，是不是逻辑有些问题：
if (l = heapsizeA[l]A[i])
largest = l;
假如数组A长度为8的时候 。当i为4的时候java实现优先队列代码，l为8java实现优先队列代码，java实现优先队列代码你去判断A[8]A[4],A[8]这里数组越界了吧 。
java 优先队列（priority queue）中，提取第二优先级的值并删除，但是不删除第一优先值的数，怎么实现？你要的是这样的效果么
public static void main(String[] args) {
PriorityQueueInteger pq = new PriorityQueueInteger();
pq.add(5);
pq.add(2);
pq.add(3);
pq.add(4);
System.out.println("取出了" pq.poll() ",队列剩余" Arrays.toString(pq.toArray()));
/**
* 假设3是我不满意的值，我要取到3后面的值
*/
if(pq.peek()==3){
System.out.println("3真不是我想要的，我可以接着往下处理么?ok,将3先保留吧");
int a = pq.poll();//将当前的第一级优先的值暂存下来，等第二级优先的值取出后再将其加入
pq.poll();
pq.add(a);
System.out.println("队列剩余" Arrays.toString(pq.toArray()));
}
System.out.println("取出了" pq.poll() ",队列剩余" Arrays.toString(pq.toArray()));
}
打印效果:
取出了2,队列剩余[3, 4, 5]
3真不是我想要的，我可以接着往下处理么?ok,将3先保留吧
队列剩余[3, 5]
取出了3,队列剩余[5]
我觉得这个是优先队列，虽然poll时候会将优先级高的数据先取出，但是同样的，如果加进去是高优先级的数据 下次取的时候它依然还是高优先级的数据 。
如何在Java中建立一优先队列java.util.PriorityQueue
这是java自带的，要自己建看它的源码即可
Java ！ 帮我定义一个优先队列（priority queue）PriorityQueueString queue= new PriorityQueueString();
//定义优先队列，此处用了泛型.下面是添加元素：
queue.add("1");
queue.add("2");
queue.add("3");
关于java实现优先队列代码和java实现优先队列代码怎么写的介绍到此就结束了 ， 不知道你从中找到你需要的信息了吗 ？如果你还想了解更多这方面的信息，记得收藏关注本站 。

    推荐阅读


    上一篇：服装店如何营销吸引顾客，服装店宣传语吸引顾客

    下一篇：阿里云服务器爬虫ip，阿里云服务器部署python爬虫