概述
普通的队列是一种先进先出的数据结构，元素在队列尾追加，而从队列头删除。在某些情况下，我们可能需要找出队列中的最大值或者最小值，例如使用一个队列保存计算机的任务，一般情况下计算机的任务都是有优先级的，我们需要在这些计算机的任务中找出优先级最高的任务先执行，执行完毕后就需要把这个任务从队列中移除。普通的队列要完成这样的功能，需要每次遍历队列中的所有元素，比较并找出最大值，效率不是很高，这个时候，我们就可以使用优先队列来完成这种需求。
优先队列按照其作用不同，可以分为以下三种：
-
最大优先队列：可以获取并删除队列中最大的值。
-
最小优先队列：可以获取并删除队列中最小的值。
-
索引优先队列：可以根据索引去操作队列中元素的值。
最大优先队列的实现就是堆的实现。最小优先队列可以通过改变推的判断条件改变。
索引优先队列
最大优先队列和最小优先队列，它们可以分别快速访问到队列中最大元素和最小元素，但是没有办法通过索引访问已存在于优先队列中的对象，并更新它们。
实现思路：
步骤一：存储数据时，给每一个数据元素关联一个整数，例如 insert(int k,T t) 可以看做k是t关联的整数，那么通过k这个值，快速获取到队列中t这个元素，此时有个k这个值需要具有唯一性。最直观的想法就是可以用一个 T[] items 数组来保存数据元素，在 insert(int k,T t) 完成插入时，可以把k看做是 items 数组的索引，把t元素放到items数组的索引k处，这样再根据k获取元素t时就很方便，直接就可以拿到 items[k]即可。
步骤二：步骤一完成后的结果，虽然给每个元素关联了一个整数，并且可以使用这个整数快速的获取到该元素，但是， items数组中的元素顺序是随机的，并不是堆有序的，所以可以增加一个数组int[]pq 来保存每个元素在items数组中的索引，pq数组需要堆有序，也就是说，pq[1]对应的数据元素items[pq[1]]要小于等于pq[2]和pq[3]对应的数据元素items[pq[2]]和items[pq[3]]。
步骤三：通过步骤二的分析，通过上浮和下沉做堆调整的时候，其实调整的是pq数组。如果需要对items中的元素进行修改，比如让items[0]=12,那么很显然，我们需要对pq中的数据做堆调整，而且是调整 pq[5]中元素的位置。但现在就会遇到一个问题，我们修改的是items数组中0索引处的值，如何才能快速的知道需要挑中pq[5]中元素的位置呢？最直观的想法就是遍历pq数组，拿出每一个元素和0做比较，如果当前元素是0，那么调整该索引处的元素即可， 但是效率很低。我们可以另外增加一个数组int[] qp用来存储pq的逆序。例如： 在pq数组中：pq[2]=7; 那么在qp数组中，把7作为索引，2作为值，结果是：qp[7]=2。
当有了pq数组后，如果我们修改items[0]=12，那么就可以先通过索引0，在qp数组中找到qp的索引：qp[0]=5，那么直接调整pq[5]即可。
public class IndexMinPriorityQueue {
private Double[] items;
private int[] pq;
private int[] qp;
private int n;
public IndexMinPriorityQueue(int capacity) {
items = new Double[capacity + 1];
pq = new int[capacity + 1];
qp = new int[capacity + 1];
n = 0;
for (int i = 0; i < qp.length; i++) {
qp[i] = -1;
}
}
//返回队列大小
public int size() {
return n;
}
//比较i和j处值的大小
private boolean less(int i, int j) {
return items[pq[i]] < items[pq[j]];
}
//判断队列是否为空
public boolean isEmpty() {
return n == 0;
}
//交换i和j处的值
private void exch(int i, int j) {
int temp = pq[i];
pq[i] = pq[j];
pq[j] = temp;
qp[pq[i]] = i;
qp[pq[j]] = j;
}
//判断k对应的元素是否存在
public boolean contains(int k) {
return qp[k] != -1;
}
//最小元素关联的索引
public int minIndex() {
return pq[1];
}
//上浮算法，使索引k处的元素能在堆中处于一个正确的位置
private void swim(int k) {
// 如果没有父结点，就不再上浮
while (k > 1) {
// 如果当前节点比父结点小，就交换
if (less(k, k / 2)) {
exch(k, k / 2);
}
k = k / 2;
}
}
//使用下沉算法，使索引k处的元素能在堆中处于一个正确的位置
private void sink(int k) {
// 如果没有子结点，就不需要下沉
while (k * 2 <= n) {
// 找出子结点中最小值的索引
int minIndex = 2 * k;
// 如果有右结点，并且右结点小于左节点
if (k * 2 + 1 <= n && less(k * 2 + 1, k * 2)) {
minIndex = 2 * k + 1;
}
// 如果当前节点小于子节点中的最小值，则结束循环
if (less(k, minIndex)) {
break;
}
// 当前节点大，交换
exch(minIndex, k);
;
k = minIndex;
}
}
//往队列中插入一个元素，并关联索引
public void insert(int i, double t) {
// 判断一下当前索引是否存在元素
if (contains(i)) {
System.out.println("当前索引" + i + "已存在元素");
return;
}
// 不存在，插入
// 格式+1
n++;
// 把t存放到索引i处
items[i] = t;
// 使pq存放i这个索引
pq[n] = i;
// qp和pq是相反的，在qp的i处存放n这个数据
qp[i] = n;
// 元素存放完毕，上浮算法
swim(n);
}
//删除队列中最小元素，并返回该元素关联的索引
public Integer delMin() {
// 最小元素的索引位置
int minIndex = pq[1];
// 交换pq中索引1处和索引n处的值
exch(1, n);
// 删除qp中索引pq[n]处的值
qp[pq[n]] = -1;
// 删除pq中索引n处的值
pq[n] = -1;
// 删除items中最小的元素
items[minIndex] = null;
n--;
// 下浮
sink(1);
return minIndex;
}
//把与索引i关联的元素修改为t
public void changeItem(int i, double t) {
items[i] = t;
// 找到i在pq中的位置
int k = qp[i];
// 对pq[k]做下沉，让堆有序
sink(k);
// 对pq[k]做上浮，让堆有序
swim(k);
}
//删除索引i关联的元素
public void delete(int i) {
// 找出i在pq中的索引
int k = qp[i];
// 把pq中索引k处的值和索引n处的值交换
exch(k, n);
// 删除qp中索引pq[n]的值
qp[pq[n]] = -1;
// 删除pq中索引n处的值
pq[n] = -1;
// 删除items中i的位置的值
items[i] = null;
// 元素数量-1
n--;
sink(k);
swim(k);
}
}
评论区