一、默认优先级
 
我们知道了队列是先进先出，那么优先队列则不一样了，进的顺序不能决定出的顺序，优先队列出的顺序是按照自己设置的优先等级来出队列的，如果自己不设置优先级的话，默认优先级为越大优先级越高。
 
例如：
 
#include <iostream>
#include <queue>
using namespace std;
priority_queue<int>que;
int main()
{
	que.push(1);
	que.push(3);
	que.push(5);
	que.push(4);
	que.push(2);
	while(!que.empty())
	{
		cout<<que.top()<<endl;
		que.pop();
	}
	return 0;
	
}
//输出结果为5、4、3、2、1
 
二、优先级的设置
 
我们知道既然默认的优先级是越大优先级越高，那么我们如何来更改这个优先级呢？
 
1、int型
 
priority_queue <int ,vector <int >, greater <int > > que ;
 priority_queue <int ,vector <int >,less <int > > que ;
 
测试代码如下：
 
#include <iostream>
#include <queue>//所需头文件 
#include <vector>//所需头文件 
using namespace std;
int main()
{
	priority_queue<int,vector<int>,less<int> >que1;//输出结果从大到小排序 
	priority_queue<int,vector<int>,greater<int> >que2;//输出结果从小到大排序 
	que1.push(1);
	que1.push(5);
	que1.push(3);
	que1.push(2);
	que1.push(4);
	que2.push(1);
	que2.push(5);
	que2.push(3);
	que2.push(2);
	que2.push(4);
	cout<<"que1: ";
	while(!que1.empty())
	{
		cout<<que1.top()<<" ";
		que1.pop();
	}
	cout<<endl;
	cout<<"que2: ";
	while(!que2.empty())
	{
		cout<<que2.top()<<" ";
		que2.pop();
	}
	cout<<endl;
	return 0;
}
/*输出结果为：que1: 5 4 3 2 1 
            que2: 5 4 3 2 1
*/ 
 
2、结构体型（和sort结构体排序的cmp类似）
 
struct node
{
int c,d;
};
bool operator <( const node & a, const node & b)//重载运算符
{
if(a.c==b.c) return a.d<b.d;
return a.c<b.c;
}
priority_queue <node > que ;
 
测试代码：
 
#include <iostream>
#include <queue>
using namespace std;
struct node
{
	int n,m;
	friend bool operator< (const node &a,const node &b)
	{
		if(a.m!=b.m) return a.m>b.m;//若m不相同，则m小的放在前面（与正常逻辑相反）
		return a.n<b.n;//若m相同，则n大的放在前面（与正常逻辑相反） 
	} 
}N[1000];
int main()
{
	priority_queue<node> que;
	for(int i=0;i<6;i++)
	{
		cin>>N[i].n>>N[i].m;
		que.push(N[i]);
	}
	while(!que.empty())
	{
		cout<<"n: "<<que.top().n<<" m: "<<que.top().m<<endl;//先进先出
		que.pop(); 
	}
	while(!que.empty()) que.pop();//清空 
	return 0;
}
 
运行结果：
 
 
关于结构体优先级的设置可以参照HDU1873题 看病要排队
 
链接：https://blog.csdn.net/KK_2018/article/details/81259019

 
java 优先队列
 

  

  

 
 
Every now and then we need to process items of a queue in a particular order. Priority queue is a Data Structure that does the job. Java priority queue is different from “normal” queue. Instead of “First-In-First-Out”, it retrieves the items in order of their priority.
 
 我们有时需要按特定顺序处理队列中的项目。 优先级队列是完成任务的数据结构。 Java优先级队列与“普通” 队列不同 。 代替“先进先出”，它按优先级顺序检索项目。 
 
 
 优先队列Java (Priority Queue Java)
 
 
The java.util.PriorityQueue class, provides us an implementation of such a data type, by using priority heap implementation internally. Java PriorityQueue is an unbounded queue. It was introduced in Java 1.5 and enhanced in Java SE 8 release. PriorityQueue is internally implemented by following “Priority Heap” data structure.
 
 java.util.PriorityQueue类通过内部使用优先级堆实现为我们提供了这种数据类型的实现。 Java PriorityQueue是一个无界队列。 它是在Java 1.5中引入的，并在Java SE 8版本中得到了增强。 PriorityQueue通过遵循“ Priority Heap”数据结构在内部实现。 
 
 

 
 
 
Here is the PriorityQueue class hierarchy:
 
 这是PriorityQueue类层次结构： 
 
 
PriorityQueue Class Diagram:
 
 PriorityQueue类图： 
 
 

  

  

 
 
 Java PriorityQueue构造函数 (Java PriorityQueue Constructors)
 
 
PriorityQueue() – Creates a PriorityQueue with the default initial capacity, i.e. 11
 PriorityQueue（） –使用默认初始容量（即11 ）创建一个PriorityQueue 
PriorityQueue(Collection c) – Creates a PriorityQueue with the elements in the specified collection
 PriorityQueue（Collection c） –使用指定集合中的元素创建一个PriorityQueue 
PriorityQueue(int initialCapacity) – Creates a PriorityQueue with the specified initial capacity
 PriorityQueue（int initialCapacity） –创建具有指定初始容量的PriorityQueue 
PriorityQueue(int initialCapacity, Comparator comparator) – Creates a PriorityQueue with the provided initial capacity and the ordering of its elements is according to the specified comparator
 PriorityQueue（int initialCapacity，Comparator比较器） –创建具有提供的初始容量的PriorityQueue，其元素的顺序根据指定的比较器 
PriorityQueue(PriorityQueue c) – Creates a PriorityQueue containing the elements in the specified priority queue
 PriorityQueue（PriorityQueue c） –创建一个包含指定优先级队列中元素的PriorityQueue 
PriorityQueue(SortedSet c) – Creates a PriorityQueue containing the elements in the specified sorted set
 PriorityQueue（SortedSet c） –创建一个包含指定排序集中的元素的PriorityQueue 
 
Priority Queue elements are ordered by their natural ordering unless we provide a Comparator while creating it.
 The elements are ordered in ascending order by default, hence the head of the queue is the element whose priority is lowest.
 
 除非我们在创建Comparator时提供它，否则Priority Queue元素将按照其自然顺序进行排序。 
 默认情况下，元素按升序排列，因此队列的开头是优先级最低的元素。 
 
 

  

  

 
 
If there are two elements which are eligible to become the head at the same time, this kind of ties are broken arbitrarily.
 
 如果有两个元素可以同时成为负责人，则这种联系会被任意打破。 
 
 
 Java PriorityQueue示例 (Java PriorityQueue Example)
 
 
Let’s create a PriorityQueue, containing various tasks:
 
 让我们创建一个PriorityQueue ，其中包含各种任务： 
 
 
PriorityQueue tasks=new PriorityQueue();
tasks.add("task1");
tasks.add("task4");
tasks.add("task3");
tasks.add("task2");
tasks.add("task5");
 
This creates a PriorityQueue of tasks, which will be ordered by the natural ordering of String.
 Let’s create another PriorityQueue which orders the tasks in reverse order of natural ordering. So we need to pass a Comparator:
 
 这将创建一个PriorityQueue任务，该任务将按String的自然顺序进行排序。 
 让我们创建另一个PriorityQueue，它以自然顺序的相反顺序对任务进行排序。 因此，我们需要通过一个比较器： 
 
 
PriorityQueue reverseTasks=new PriorityQueue(Comparator.reverseOrder());
reverseTasks.add("task1");
reverseTasks.add("task4");
reverseTasks.add("task3");
reverseTasks.add("task2");
reverseTasks.add("task5");
 
 Java PriorityQueue方法 (Java PriorityQueue Methods)
 
 
Now, let’s take a look at all the methods available for PriorityQueue and use them:
 
 现在，让我们看一下PriorityQueue可用的所有方法并使用它们： 
 
 
Boolean add(E e) – This method inserts the specified element in the queue.
 We have already added 5 tasks in our queue using this method.
 布尔值add（E e） –此方法将指定的元素插入队列。 
 我们已经使用这种方法在队列中添加了5个任务。 
Comparator comparator() – This method returns the Comparator used to order the elements in this queue. It returns null if no comparator was specified and the queue is sorted according to the natural ordering of its elements.
 So, if we do:
System.out.println(tasks.comparator());
System.out.println(reverseTasks.comparator());
The output will be:
 比较器比较器（） -此方法返回用于对队列中的元素进行排序的比较器 。 如果未指定比较器，并且队列根据其元素的自然顺序排序，则返回null。 
 因此，如果我们这样做： 
System.out.println(tasks.comparator());
System.out.println(reverseTasks.comparator());
 
 输出将是： 
 
boolean contains(Object o) – Returns true if the queue contains the specified element.
 Let’s check if “task3” belongs to the Priority queue tasks:
System.out.println(tasks.contains("task3"));
This prints:
 boolean contains（Object o） –如果队列包含指定的元素，则返回true。 
 让我们检查“ task3”是否属于优先级队列任务： 
System.out.println(tasks.contains("task3"));
 
 打印： 
 
boolean offer(E e) – Just like the add() method, this method also adds an element to the queue.
 The offer() and add() methods are actually a bit different for capacity constrained queues, but in case of PriorityQueue, both are same. Unlike add(), offer() does not throw an exception even if it fails to add the element in the queue.
 boolean offer（E e） –就像add（）方法一样，此方法也将元素添加到队列中。 
 对于容量受限制的队列，offer（）和add（）方法实际上有些不同，但是对于PriorityQueue，两者是相同的。 与add（）不同，即使offer（）无法将元素添加到队列中，它也不会引发异常。 
E peek() – Retrieves the head of this queue, or returns null if this queue is empty. In other words, it returns the element with highest priority.
 So the following code:
System.out.println(tasks.peek());
System.out.println(reverseTasks.peek());
Gives us:
 E peek（） –检索此队列的开头，如果此队列为空，则返回null。 换句话说，它返回具有最高优先级的元素。 
 所以下面的代码： 
System.out.println(tasks.peek());
System.out.println(reverseTasks.peek());
 
 给我们： 
 
E poll() – This method also retrieves the head of the queue(element with highest priority), or returns null if the queue is empty. But unlike peek(), it also removes the element.
 So, if we call poll():
System.out.println(“Poll on tasks: ”+tasks.poll());
System.out.println(“Poll on reverseTasks: ”+reverseTasks.poll());
And then peek:
We’ll have the following outptut:
Poll on tasks: task1
Poll on reverseTasks: task5
Peek on tasks: task2
Peek on reverseTasks: task4
 E poll（） –此方法还检索队列的头部（具有最高优先级的元素），如果队列为空，则返回null。 但是与peek（）不同，它还删除了元素。 
 因此，如果我们调用poll（）： 
 然后偷看： 
 
System.out.println(“Peek on tasks: ”+tasks.peek());
System.out.println(“Peek on reverseTasks: ”+reverseTasks.peek());
 
 我们将提供以下输出： 
 
int size() – Returns the number of elements in the queue.
 int size（） –返回队列中元素的数量。 
boolean remove(Object o) – Removes the specified element from the queue, if it’s present. If two same elements are present, it only removes one of them.
 boolean remove（Object o） -从队列中删除指定的元素（如果存在）。 如果存在两个相同的元素，则仅删除其中之一。 
Object[] toArray() – Returns an array containing all the elements in the queue.
 Object [] toArray（） –返回包含队列中所有元素的数组。 
T[] toArray(T[] a) – Returns an array containing all the elements in the queue, and the type of the returned array is that of the specified array.
 T [] toArray（T [] a） –返回包含队列中所有元素的数组，并且返回的数组的类型为指定数组的类型。 
Iterator iterator() – Returns an iterator for the queue.
 Iterator iterator（） –返回队列的迭代器。 
void clear() – Removes all of the elements from the queue.
 void clear（） –从队列中删除所有元素。 
 
Apart from these, the PriorityQueue also inherits the methods from the Collection and Object classes.
 
 除此之外， PriorityQueue还继承了Collection和Object类的方法。 
 
 
 Java PriorityQueue时间复杂度 (Java PriorityQueue Time Complexity)
 
 
For enqueing and dequeing methods, the time complexity is O(log(n))
 对于入队和出队方法，时间复杂度为O（log（n）） 
For the remove(Object) and contains(Object) methods, the time complexity is linear
 对于remove（Object）和contains（Object）方法，时间复杂度是线性的 
For the retrieval methods, it has constant time complexity
 对于检索方法，它具有恒定的时间复杂度 
 
This implementation of priority queue is not thread-safe. So, if we need synchronised access, we need to use PriorityBlockingQueue.
 
 优先级队列的此实现不是线程安全的。 因此，如果需要同步访问，则需要使用PriorityBlockingQueue 。 
 
 
Reference: API Doc
 
 参考： API文档 
 
 

  
翻译自: https://www.journaldev.com/16254/priority-queue-java
 
 
java 优先队列

优先队列
 
普通的队列是一种先进先出的数据结构，元素在队列尾追加，而从队列头删除。在某些情况下，我们可能需要找出 队列中的最大值或者最小值，例如使用一个队列保存计算机的任务，一般情况下计算机的任务都是有优先级的，我 们需要在这些计算机的任务中找出优先级最高的任务先执行，执行完毕后就需要把这个任务从队列中移除。普通的 队列要完成这样的功能，需要每次遍历队列中的所有元素，比较并找出最大值，效率不是很高，这个时候，我们就 可以使用一种特殊的队列来完成这种需求，优先队列。
 
优先队列按照其作用不同，可以分为以下两种：
 
最大优先队列：
 可以获取并删除队列中最大的值
 
最小优先队列：
 可以获取并删除队列中最小的值
 
一 最大优先队列
 
我们之前学习过堆，而堆这种结构是可以方便的删除最大的值，所以，接下来我们可以基于堆区实现最大优先队 列。
 
1.1最大优先队列API设计
 
类名
MaxPriorityQueue<T extends Comparable>
构造方法
MaxPriorityQueue(int capacity)：创建容量为capacity的MaxPriorityQueue对象
成员方法
1.private boolean less(int i,int j)：判断堆中索引i处的元素是否小于索引j处的元素
 2.private void exch(int i,int j):交换堆中i索引和j索引处的值
 3.public T delMax():删除队列中最大的元素,并返回这个最大元素
4.public void insert(T t)：往队列中插入一个元素 
5.private void swim(int k):使用上浮算法，使索引k处的元素能在堆中处于一个正确的位置
 6.private void sink(int k):使用下沉算法，使索引k处的元素能在堆中处于一个正确的位置 
7.public int size():获取队列中元素的个数
 8.public boolean isEmpty():判断队列是否为空
成员变量
1.private T[] imtes : 用来存储元素的数组
 2.private int N：记录堆中元素的个数
1.2 最大优先队列代码实现
 
1.2.1主要方法
 
public class MaxPriorityQueue<T extends Comparable<T>> {
//用来存储元素的数组
private T[] items;
//记录元素个数
private int N;
}
 
//创建容量为capacity的MaxPriorityQueue对象
public MaxPriorityQueue(int capacity) {
    this.N = 0;
    this.items = (T[]) new Comparable[capacity + 1];
}
 
//判断堆中索引i处的元素是否小于索引j处的元素
private boolean less(int i, int j) {
    return items[i].compareTo(items[j]) < 0;
}
 
//交换堆中i索引和j索引处的值
private void exchange(int i, int j) {
    T temp = items[i];
    items[i] = items[j];
    items[j] = temp;
}
 
//获取队列中元素的个数
public int size() {
    return N;
}

//判断队列是否为空
public boolean isEmpty() {
    return N == 0;
}
 
//：往队列中插入一个元素
public void insert(T t) {
    items[++N] = t;
    swim(N);
}

//使用上浮算法，使索引k处的元素能在堆中处于一个正确的位置
private void swim(int k) {
    //如果已经到了根结点，就不需要循环
    while (k > 1) {
        if (less(k / 2, k)) {
            exchange(k / 2, k);
        }
        k = k / 2;
    }
}
 
//删除堆中最大的元素,并返回这个最大元素
public T delMax() {
    T max = items[1];
    //交换索引1处和索引N处的值
    exchange(1, N);
    items[N] = null;
    N--;
    sink(1);
    return max;
}

//使用下沉算法，使索引k处的元素能在堆中处于一个正确的位置
private void sink(int k) {
    //如果当前已经是最底层了，就不需要循环了
    while (2 * k <= N) {
        int max = 2 * k;
        if (max + 1 <= N) {//表示有右子节点
            if (less(max, max + 1)) {
                max = max + 1;
            }
        }
        //比较当前结点和子结点中的较大者，如果当前结点不小，则结束循环
        if (!less(k,max)){
            break;
        }
        //当前结点小，则交换，
        exchange(k,max);
        k = max;
    }
}
 
1.2.2源代码
 
/**
 * 最大优先队列数组实现
 *
 * @author 毛毛
 */
public class MaxPriorityQueue<T extends Comparable<T>> {
    //用来存储元素的数组
    private T[] items;
    //记录元素个数
    private int N;

    //创建容量为capacity的MaxPriorityQueue对象
    public MaxPriorityQueue(int capacity) {
        this.N = 0;
        this.items = (T[]) new Comparable[capacity + 1];
    }

    //判断堆中索引i处的元素是否小于索引j处的元素
    private boolean less(int i, int j) {
        return items[i].compareTo(items[j]) < 0;
    }

    //交换堆中i索引和j索引处的值
    private void exchange(int i, int j) {
        T temp = items[i];
        items[i] = items[j];
        items[j] = temp;
    }

    //获取队列中元素的个数
    public int size() {
        return N;
    }

    //判断队列是否为空
    public boolean isEmpty() {
        return N == 0;
    }

    //：往队列中插入一个元素
    public void insert(T t) {
        items[++N] = t;
        swim(N);
    }

    //使用上浮算法，使索引k处的元素能在堆中处于一个正确的位置
    private void swim(int k) {
        //如果已经到了根结点，就不需要循环
        while (k > 1) {
            if (less(k / 2, k)) {
                exchange(k / 2, k);
            }
            k = k / 2;
        }
    }

    //删除堆中最大的元素,并返回这个最大元素
    public T delMax() {
        T max = items[1];
        //交换索引1处和索引N处的值
        exchange(1, N);
        items[N] = null;
        N--;
        sink(1);
        return max;
    }

    //使用下沉算法，使索引k处的元素能在堆中处于一个正确的位置
    private void sink(int k) {
        //如果当前已经是最底层了，就不需要循环了
        while (2 * k <= N) {
            int max = 2 * k;
            if (max + 1 <= N) {//表示有右子节点
                if (less(max, max + 1)) {
                    max = max + 1;
                }
            }
            //比较当前结点和子结点中的较大者，如果当前结点不小，则结束循环
            if (!less(k,max)){
                break;
            }
            //当前结点小，则交换，
            exchange(k,max);
            k = max;
        }
    }
}
 
二 最小优先队列
 
最小优先队列实现起来也比较简单，我们同样也可以基于堆来完成最小优先队列。
 我们前面学习堆的时候，堆中存放数据元素的数组要满足都满足如下特性：
 
1.最大的元素放在数组的索引1处。
 2.每个结点的数据总是大于等于它的两个子结点的数据。
 
其实我们之前实现的堆可以把它叫做最大堆，我们可以用相反的思想实现最小堆，让堆中存放数据元素的数组满足 如下特性：
 
1.最小的元素放在数组的索引1处。
 2.每个结点的数据总是小于等于它的两个子结点的数据。
 
2.1最小优先队列API设计
 
类名
MinPriorityQueue<T extends Comparable>
构造方法
MinPriorityQueue(int capacity)：创建容量为capacity的MinPriorityQueue对象
成员方法
1.private boolean less(int i,int j)：判断堆中索引i处的元素是否小于索引j处的元素
 2.private void exch(int i,int j):交换堆中i索引和j索引处的值 
3.public T delMin():删除队列中最小的元素,并返回这个最小元素 
4.public void insert(T t)：往队列中插入一个元素 
5.private void swim(int k):使用上浮算法，使索引k处的元素能在堆中处于一个正确的位置
 6.private void sink(int k):使用下沉算法，使索引k处的元素能在堆中处于一个正确的位置 
7.public int size():获取队列中元素的个数
 8.public boolean isEmpty():判断队列是否为空
成员变量
1.private T[] imtes : 用来存储元素的数组
 2.private int N：记录堆中元素的个数
2.2 最小优先队列代码实现
 
/**
 * 最小优先队列，用最小堆
 *
 * @author 毛毛
 */
public class MinPriorityQueue<T extends Comparable<T>> {
    //用来存储元素的数组
    private T[] items;
    //记录堆中元素的个数
    private int N;

    //创建容量为capacity的MinPriorityQueue对象
    public MinPriorityQueue(int capacity) {
        this.N = 0;
        this.items = (T[]) new Comparable[capacity + 1];
    }

    //:获取队列中元素的个数
    public int size() {
        return N;
    }

    //:判断队列是否为空
    public boolean isEmpty() {
        return N == 0;
    }

    //:交换堆中i索引和j索引处的值
    private void exchange(int i, int j) {
        T temp = items[i];
        items[i] = items[j];
        items[j] = temp;
    }

    //判断堆中索引i处的元素是否小于索引j处的元素
    private boolean less(int i, int j) {
        return items[i].compareTo(items[j]) < 0;
    }

    //往队列中插入一个元素
    public void insert(T t) {
        items[++N] = t;
        swim(N);
    }

    //使用上浮算法，使索引k处的元素能在堆中处于一个正确的位置
    private void swim(int k) {
        //如果没有父结点，则不再上浮
        while (k > 1) {
            //如果当前结点比父结点小，则交换
            if (less(k, k / 2)) {
                exchange(k, k / 2);
            }
            k = k / 2;
        }
    }

    //删除队列中最小的元素,并返回这个最小元素
    public T delMin() {
        T min = items[1];
        exchange(1, N);
        items[N] = null;
        N--;
        sink(1);
        return min;
    }

    //使用下沉算法，使索引k处的元素能在堆中处于一个正确的位置
    private void sink(int k) {
        //如果没有子结点，则不再下沉
        while (2 * k <= N) {
            int min = 2 * k;
            if (min + 1 <= N) {//条件成立说明有右子节点
                //找出子结点中的较小值的索引
                if (!less(min, min + 1)) {
                    min = min + 1;
                }
            }
            //如果当前结点小于子结点中的较小值，则结束循环
            if (less(k, min)) {
                break;
            }
            //当前结点大，交换
            exchange(k, min);
            k = min;
        }
    }

}
 
三 索引优先队列
 
在之前实现的最大优先队列和最小优先队列，他们可以分别快速访问到队列中最大元素和最小元素，但是他们有一 个缺点，就是没有办法通过索引访问已存在于优先队列中的对象，并更新它们。为了实现这个目的，在优先队列的 基础上，学习一种新的数据结构，索引优先队列。接下来我们以最小索引优先队列举列。
 
3.1 索引优先队列实现思路
 
步骤一：
 
存储数据时，给每一个数据元素关联一个整数，例如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]即可。
 
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-ToxymrZi-1596879285752)(F:\MarkDown\笔记\Java博客\Java博客图片\索引优先队列1.png)]
 
步骤二：
 
步骤一完成后的结果，虽然我们给每个元素关联了一个整数，并且可以使用这个整数快速的获取到该元素，但是， items数组中的元素顺序是随机的，并不是堆有序的，所以，为了完成这个需求，我们可以增加一个数组int[]pq,来 保存每个元素在items数组中的索引，pq数组需要堆有序，也就是说，pq[1]对应的数据元素items[pq[1]]要小于等 于pq[2]和pq[3]对应的数据元素items[pq[2]]和items[pq[3]]。
 
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-W1OA0P2c-1596879285753)(F:\MarkDown\笔记\Java博客\Java博客图片\索引优先队列2.png)]
 
步骤三：
 
通过步骤二的分析，我们可以发现，其实我们通过上浮和下沉做堆调整的时候，其实调整的是pq数组。如果需要 对items中的元素进行修改，比如让items[0]=“H”,那么很显然，我们需要对pq中的数据做堆调整，而且是调整 pq[9]中元素的位置。但现在就会遇到一个问题，我们修改的是items数组中0索引处的值，如何才能快速的知道需 要挑中pq[9]中元素的位置呢？
 最直观的想法就是遍历pq数组，拿出每一个元素和0做比较，如果当前元素是0，那么调整该索引处的元素即可， 但是效率很低。
 
我们可以另外增加一个数组，int[] qp,用来存储pq的逆序。例如：
 在pq数组中：pq[1]=6;
 
那么在qp数组中[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-Hm0tSa1N-1596879285754)(F:\MarkDown\笔记\Java博客\Java博客图片\索引优先队列3.png)]，把6作为索引，1作为值，结果是：qp[6]=1;
 
当有了pq数组后，如果我们修改items[0]=“H”，那么就可以先通过索引0，在qp数组中找到qp的索引：qp[0]=9, 那么直接调整pq[9]即可。
 
3.2索引优先队列API设计
 
类名
IndexMinPriorityQueue<T extends Comparable>
构造方法
IndexMinPriorityQueue(int capacity)：创建容量为capacity的IndexMinPriorityQueue对象
成员方法
1.private boolean less(int i,int j)：判断堆中索引i处的元素是否小于索引j处的元素 
2.private void exch(int i,int j):交换堆中i索引和j索引处的值 
3.public int delMin():删除队列中最小的元素,并返回该元素关联的索引 
4.public void insert(int i,T t)：往队列中插入一个元素,并关联索引i 
5.private void swim(int k):使用上浮算法，使索引k处的元素能在堆中处于一个正确的位置 
6.private void sink(int k):使用下沉算法，使索引k处的元素能在堆中处于一个正确的位置 
7.public int size():获取队列中元素的个数
8.public boolean isEmpty():判断队列是否为空 
9.public boolean contains(int k):判断k对应的元素是否存在
10.public void changeItem(int i, T t):把与索引i关联的元素修改为为t 
11.public int minIndex():最小元素关联的索引 
12.public void delete(int i):删除索引i关联的元素
成员变量
1.private T[] imtes : 用来存储元素的数组
 2.private int[] pq:保存每个元素在items数组中的索引，pq数组需要堆有序 
3.private int [] qp:保存qp的逆序，pq的值作为索引，pq的索引作为值
4.private int N：记录堆中元素的个数
3.3索引优先队列代码实现
 
public class IndexMinPriorityQueue<T extends Comparable<T>> {
    //用来存储元素的数组
    private T[] items;
    //保存每个元素在items数组中的索引，pq数组需要堆有序
    private int[] pq;
    //保存qp的逆序，pq的值作为索引，pq的索引作为值
    private int[] qp;
    //记录堆中元素的个数
    private int N;

    //创建容量为capacity的IndexMinPriorityQueue对象
    public IndexMinPriorityQueue(int capacity) {
        this.N = 0;
        this.items = (T[]) new Comparable[capacity + 1];
        this.pq = new int[capacity + 1];
        this.qp = new int[capacity + 1];
        for (int i = 0; i < this.qp.length; i++) {
            //默认情况下，qp逆序中不保存任何索引
            qp[i] = -1;
        }
    }

    //获取队列中元素的个数
    public int size() {
        return N;
    }

    //判断队列是否为空
    public boolean isEmpty() {
        return N == 0;
    }

    //判断堆中索引i处的元素是否小于索引j处的元素
    private boolean less(int i, int j) {
        //先通过pq找出items中的索引，然后再找出items中的元素进行对比
        return items[pq[i]].compareTo(items[pq[j]]) < 0;
    }

    //交换堆pq中i索引和j索引处的值
    private void exchange(int i, int j) {
        //先交换pq数组中的值
        int temp = pq[i];
        pq[i] = pq[j];
        pq[j] = temp;
        //更新qp数组中的值
        qp[pq[i]] = i;
        qp[pq[j]] = j;
    }

    //判断k对应的元素是否存在
    public boolean contains(int k) {
        //默认情况下，qp的所有元素都为-1，如果某个位置插入了数据，则不为-1
        return qp[k] != -1;
    }

    //最小元素关联的索引
    public int minIndex() {
        //pq的索引1处，存放的是最小元素在items中的索引
        return pq[1];
    }

    //往队列中插入一个元素,并关联索引i
    public void insert(int i, T t) {
        //如果索引i处已经存在了元素，则不让插入
        if (contains(i)) {
            throw new RuntimeException("该索引已存在值");
        }
        //个数加一
        N++;
        //把元素存放到items数组中
        items[i] = t;
        //使用pq存放i这个索引
        pq[N] = i;
        //在qp的i索引处存放N
        qp[i] = N;
        //上浮items[pq[N]],让pq堆有序
        swim(N);
    }

    //使用上浮算法，使索引k处的元素能在堆中处于一个正确的位置
    private void swim(int k) {
        //如果已经到了根结点，则结束上浮
        while (k > 1) {
            if (less(k, k / 2)) {
                //比较当前结点和父结点，如果当前结点比父结点小，则交换位置
                exchange(k, k / 2);
            }
            k = k / 2;
        }
    }

    //删除队列中最小的元素,并返回该元素关联的索引
    public int delMin() {
        //找到items中最小元素的索引
        int minIndex = pq[1];
        //交换pq中索引1处的值和N处的值
        exchange(1, N);
        //删除qp中索引pq[N]处的值
        qp[pq[N]] = -1;
        //删除pq中索引N处的值
        pq[N] = -1;
        //删除items中的最小元素
        items[minIndex] = null;
        //元素数量-1
        N--;
        //对pq[1]做下沉，让堆有序
        sink(1);
        //返回该最小元素所关联的索引（在items中的）
        return minIndex;
    }

    //使用下沉算法，使索引k处的元素能在堆中处于一个正确的位置
    private void sink(int k) {
        //如果当前结点已经没有子结点了，则结束下沉
        while (2 * k <= N) {
            //找出子结点中的较小值
            int min = 2 * k;
            if (min + 1 <= N) {
                if (!less(min, min + 1)) {
                    min = min + 1;
                }
            }
            //如果当前结点的值比子结点中的较小值小，则结束下沉
            if (less(k, min)) {
                break;
            }
            exchange(k, min);
            k = min;
        }
    }

    //删除索引i关联的元素
    public void delete(int i) {
        //找出i在pq中的索引
        int k = qp[i];
        //把pq中索引k处的值和索引N处的值交换
        exchange(k, N);
        //删除qp中索引pq[N]处的值
        qp[pq[N]] = -1;
        //删除pq中索引N处的值
        pq[N] = -1;
        //删除items中索引i处的值
        items[i] = null;
        //元素数量-1
        N--;
        //对pq[k]做下沉，让堆有序
        sink(k);
        //对pq[k]做上浮，让堆有序
        swim(k);
    }

    //把与索引i关联的元素修改为为t
    public void changeItem(int i, T t) {
        //修改items数组中索引i处的值为t
        items[i] = t;
        //找到i在pq中的位置
        int k = qp[i];
        //对pq[k]做下沉，让堆有序
        sink(k);
        //对pq[k]做上浮，让堆有序
        swim(k);
    }
}
        //删除qp中索引pq[N]处的值
        qp[pq[N]] = -1;
        //删除pq中索引N处的值
        pq[N] = -1;
        //删除items中索引i处的值
        items[i] = null;
        //元素数量-1
        N--;
        //对pq[k]做下沉，让堆有序
        sink(k);
        //对pq[k]做上浮，让堆有序
        swim(k);
    }

    //把与索引i关联的元素修改为为t
    public void changeItem(int i, T t) {
        //修改items数组中索引i处的值为t
        items[i] = t;
        //找到i在pq中的位置
        int k = qp[i];
        //对pq[k]做下沉，让堆有序
        sink(k);
        //对pq[k]做上浮，让堆有序
        swim(k);
    }
}