目录
前言
上一个博客实现的最大优先队列和最小优先队列,他们可以分别快速访问到队列中最大元素和最小元素,但是他们有一个缺点,就是没有办法通过索引访问已存在于优先队列中的对象,并更新。 为了实现这个目的,在优先队列的基础上,学习一种新的数据结构, 索引优先队列 。接下来我们以最小索引优先队列举列。 原理:以空间换时间,利用 两个辅助数组来维护优先队列。实现步骤
步骤一: 存储数据时,给每一个数据元素关联一个整数,例如insert(int k,T t)。例如 可以用一个 T[] items 数组来保存数据元素,在 insert(int k,T t) 完成插入时,可以把 k 看做是 items 数组的索引, 把t元素放到items数组的索引k处 。 步骤二: 步骤一完成后的结果,虽然我们给每个元素关联了一个整数,但是items数组中的元素顺序是随机的,并不是堆有序的,需要增加一个数组 int[]pq, 来保存每个元素在items 数组中的索引, pq数组需要堆有序 。例如 pq[1] 对应的数据元素 items[pq[1]] 要小于等 于 pq[2] 和 pq[3] 对应的数据元 items[pq[2]] 和 items[pq[3]] 。 步骤三: 为了方便快速调整items中的元素, 构建pq数组的逆序 int[] qp,例如: 在 pq 数组中:pq[1]=6; 那么在 qp 数组中,把 6 作为索引, 1 作为值,结果是: qp[6]=1。 当有了pq数组后,如果我们修改items[0]="H",那么就可以先通过索引0,在qp数组中找到qp的索引:qp[0]=9, 那么直接调整pq[9] 即可。代码实现
代码API
package tree2;
public class IndexMinPriorityQueue <T extends Comparable<T>>{
private T[] items;
private int[] pq;
private int[] qp;
private int N;
public IndexMinPriorityQueue(int capacity){
this.items = (T[]) new Comparable[capacity+1];
this.pq = new int[capacity+1];
this.qp = new int[capacity+1];
this.N = 0;
//默认情况下,队列中没有存储任何书籍,让qp的元素都为-1
for(int i=0; i<qp.length; i++){
qp[i] =- 1;
}
}
//获取队列元素的个数
public int size(){
return N;
}
//判断队列是否为空
public boolean inEmpty(){
return N==0;
}
//判断堆中元素大小
private boolean less(int i, int j){
return items[pq[i]].compareTo(items[pq[j]])<0;
}
//交换堆中元素值
private void exch(int i, int j){
int tmp = pq[i];
pq[i] = pq[j];
pq[j] = tmp;
//更新qp中的数据
qp[pq[i]] = i;
qp[pq[j]] = j;
}
//判断k对应的元素是否存在
public boolean contains(int k){
return qp[k] != -1;
}
//最小元素关联的索引
public int minIndex(){
return pq[1];
}
//往队列中插入一个元素
public void insert(int i, T t){
// 判断i是否已经被关联,如果已经被关联,不让插入
if (contains(i)){
return;
}
N++;
//把数据存储到items对应的i位置处
items[i] = t;
// 把i存储到pq中
pq[N] = i;
// 用qp来记录pq的i
qp[i] = N;
//保持堆有序
swim(N);
}
// 删除队列中最小的元素,并返回该元素关联的索引
public int delMin(){
int minIndex = pq[1];
// 交换pq
exch(1,N);
// 删除qp中对应的内容
qp[pq[N]] = -1;
// 删除pq最大索引处的内容
pq[N] = -1;
// 删除items中对应的内容
items[minIndex] = null;
// 元素个数-1
N--;
// 下沉调整
sink(1);
return minIndex;
}
// 删除索引i关联的元素
public void delete(int i){
//找出i在pq中的索引
int k = pq[i];
exch(k,N);
qp[pq[N]] = -1;
pq[N] = -1;
items[k] = null;
N--;
// 因为元素k是在数组中的中间,所以需要先下沉再上浮,或者先上浮再下沉
sink(k);
swim(k);
}
// 修改索引i关联的元素为t
public void changeItem(int i, T t){
items[i] = t;
int k = qp[i];
sink(k);
swim(k);
}
// 上浮算法
private void swim(int k){
while(k>1){
if(less(k,k/2)){
exch(k,k/2); //这里面已经更新了pq[]和qp[]
}
k = k/2;
}
}
//下沉算法
private void sink(int k){
while(2*k<=N){
int min;
if (2*k+1<=N){
if(less(2*k,2*k+1)){
min = 2*k;
}else{
min = 2*k + 1;
}
}else{
min = 2*k;
}
//比较当前结点和较小值
if (less(k,min)){
break;
}
exch(k,min);
k = min; //把最小值赋值给当前结点
}
}
}