Java利用跳跃表解决双重队列问题详解
chengqiuming 人气:0一 问题描述
银行的每个客户都有一个正整数标识 K，到银行请求服务时将收到一个正整数的优先级 P 。银行经理提议打破传统，在某些时候调用优先级最低的客户，而不是优先级最高的客户。系统将收到以下类型的请求：
① 0，系统需要停止服务。
② 1 K P，将客户 K 及优先级 P 添加到等待列表中。
③ 2，为优先级最高的客户提供服务，并将其从等待名单中删除。
④ 3，为优先级最低的客户提供服务，并将其从等待名单中删除。
二 输入
输入的每一行都包含一个请求，只有最后一行包含停止请求（代码0）。假设有请求在列表中包含新客户（代码1），在同一客户的列表中没有其他请求或有相同的优先级，标识符 K 总是小于10^6 ，优先级 P 总是小于10^7 。一个客户可以多次到银行请求服务，但是每次都获得不同的优先级。
三 输出
对代码为 2 或 3 的每个请求都单行输出所服务客户的标识。若请求在等待列表为空时到达，则输出 0。
四 输入和输出样例
1 输入样例
2
1 20 14
1 30 3
2
1 10 99
3
2
2
0
2 输出样例
0
20
30
10
0
五 分析和设计
本问题包括插入、删除优先级最高元素和删除优先级最低元素等3种操作，可以使用跳跃表解决。
六 代码
package com.platform.modules.alg.alglib.poj3481;
import java.util.Random;
public class Poj3481D {
private int INF = 0x7fffffff;
private int MAX_LEVEL = 16;
public String output = "";
public String cal(String input) {
Init();
int op, num, val;
String[] line = input.split("\n");
int count = 0;
while (true) {
String commad[] = line[count++].split(" ");
op = Integer.parseInt(commad[0]);
if (op == 1) {
num = Integer.parseInt(commad[1]);
val = Integer.parseInt(commad[2]);
Insert(num, val);
} else if (op == 0) {
return output;
} else if (op == 2)
Delete(true);
else
Delete(false);
}
}
class Node {
int num, val;
Node forward[] = new Node[MAX_LEVEL];
}
public Poj3481D() {
for (int i = 0; i < updata.length; i++) {
updata[i] = new Node();
}
}
Node head;
Node updata[] = new Node[MAX_LEVEL];
int level, max_k, min_k;
void Init() {
level = 0;
max_k = -INF;
min_k = INF;
head = new Node();
for (int i = 0; i < MAX_LEVEL; i++)
head.forward[i] = null;
head.val = -INF;
}
// 按规则选择数据应该在哪层插入
int RandomLevel() {
int lay = 0;
while (new Random().nextInt(100) % 2 == 0 && lay < MAX_LEVEL - 1)
lay++;
return lay;
}
// 查找最接近val的元素
Node Find(int val) {
Node p = head;
for (int i = level; i >= 0; i--) {
while (p.forward[i] != null && p.forward[i].val < val)
p = p.forward[i];
updata[i] = p; // 记录搜索过程中各级走过的最大节点位置
}
return p;
}
void Insert(int num, int val) {
if (val > max_k) max_k = val;
if (val < min_k) min_k = val;
Node s;
int lay = RandomLevel();
if (lay > level) // 要插入的层 > 现有层数
level = lay;
Find(val); //查询
s = new Node(); // 创建一个新节点
s.num = num;
s.val = val;
for (int i = 0; i < MAX_LEVEL; i++)
s.forward[i] = null;
for (int i = 0; i <= lay; i++) { // 插入操作
s.forward[i] = updata[i].forward[i];
updata[i].forward[i] = s;
}
}
// flag=false 表示删除最小值，true 表示删除最大值
void Delete(boolean flag) {
int d;
if (flag) d = max_k;
else d = min_k;
if (d == -INF || d == INF) { // 说明还没有插入元素
output += "0\n";
return;
}
Node p = Find(d);
if (p.forward[0] != null && p.forward[0].val == d) {
output += String.format("%d\n", p.forward[0].num);
if (p.val == -INF && p.forward[0].forward[0] == null) // 删除唯一节点
{
max_k = -INF;
min_k = INF;
} else {
if (flag) max_k = p.val;
else min_k = p.forward[0].forward[0].val;
}
for (int i = level; i >= 0; i--) { // 删除操作
if (updata[i].forward[i] != null && updata[i].forward[i].val == d)
updata[i].forward[i] = updata[i].forward[i].forward[i];
}
}
}
}七 测试
加载全部内容