/** * @desc: 自定义索引优先队列,可修改,删除索引对应的值 * @author: 毛会懂 * @create: 2021-01-06 17:20:00 **/ public class MyIndexPriorityQueue<T extends Comparable<T>> { private T[] arr;//存储数组元素 private int[] pq;//存储元素的下标,符合堆结构 private int[] qp;//存储元素下标的堆的反序,pq数组中的值作为索引,pq数组的索引作为值j private int size; public MyIndexPriorityQueue(Integer size){ arr = (T[])new Comparable[size]; pq = new int[size + 1]; qp = new int[size + 1]; for (int i = 0; i < qp.length; i++) { //默认情况下,qp逆序中不保存任何索引 qp[i] = -1; } this.size = 0; } //队列大小 public Integer getSize(){ return size; } //是否为空 public Boolean isEmpty(){ return size == 0; } //某一个位置是否有元素 public Boolean contains(int k){ return qp[k] != -1; } //指定位置,添加元素 public void add(int i,T t){ arr[i] = t; size++; //元素的下标需要符合堆结构 pq[size] = i; qp[i] = size; swim(size); } //删除最大元素 public T delMax(){ if(size <= 0){ return null; } T t = arr[pq[1]]; change(1,size); size--; sink(1); return t; } //修改某一个位置的元素 public void update(int k ,T t){ if(!contains(k)){ return; } //修改元素值 arr[k] = t; //找到此元素在pq的下标 int index = qp[k]; //上浮 swim(index); //下沉 sink(index); } //删除某一个位置元素 public void delete(int k){ if(!contains(k)){ return; } //删除元素 arr[k] = null; //交换位置 int index = qp[k]; change(index,size); //删除下标 qp[pq[size]] = -1; pq[size] = -1; size--; //上浮 swim(index); //下沉 sink(index); } //最小元素关联的索引 public int getMinIndex(){ if(size >=1) { return pq[1]; } return -1; } //上浮 private void swim(int k){ while (k > 1){ if(great(k,k/2)){ change(k,k/2); } k = k /2; } } //下沉 private void sink(int k){ while (2 * k <= size){ int max; if(2 * k + 1 <= size) { if (great(2 * k, 2 * k + 1)) { max = 2 * k; } else { max = 2 * k + 1; } }else{ max = 2 * k; } if(great(max,k)){ change(max,k); } k = max; } } private Boolean great(int i,int j){ return arr[pq[i]].compareTo(arr[pq[j]]) > 0; } private void change(int i,int j){ int temp = pq[i]; pq[i] = pq[j]; pq[j] = temp; qp[pq[i]] = i; qp[pq[j]] = j; } }
测试代码:
//最大索引优先队列
public static void main(String[] args) {
MyIndexPriorityQueue queue = new MyIndexPriorityQueue(10);
queue.add(0,8);
queue.add(1,1);
queue.add(2,5);
queue.add(3,12);
queue.add(4,15);
queue.add(5,3);
queue.add(6,6);
queue.add(7,4);
queue.add(8,2);
queue.add(9,7);
System.out.println("最大的元素所在的索引:"+queue.getMinIndex());
System.out.println("修改元素");
// queue.update(6,"Z");
// System.out.println("删除元素");
// queue.delete(2);
for(int i = 0;i < 10;i++){
System.out.print(queue.delMax() + ", ");
}
System.out.println("over");
}
本文参考链接:https://www.cnblogs.com/maohuidong/p/14245998.html