优先队列
概述
优先队列的产生
普通的队列是一种先进先出的数据结构，元素在队列尾追加，而从队列头删除。在某些情况下，我们可能需要找出队列中的最大值或者最小值，例如使用一个队列保存计算机的任务，一般情况下计算机的任务都是有优先级的，我们需要在这些计算机的任务中找出优先级最高的任务先执行，执行完毕后就需要把这个任务从队列中移除。普通的队列要完成这样的功能，需要每次遍历队列中的所有元素，比较并找出最大值，效率不是很高，这个时候，我们就可以使用一种特殊的队列来完成这种需求，优先队列。
优先队列的划分
- 最大优先队列：每次获取并删除队列中最大的值
- 最小优先队列：每次获取并删除队列中最小的值
最大优先队列
实现思想
利用了大顶堆的思想，实现了每次删除队列中最大的值
API设计
API设计的思路以及优先队列的实现思想
- 将数据按照大顶堆的思想，依次插入，每次插入都让他进行上浮算法，使得新插入的元素在大顶堆中有序。
- 数据全部插入完成之后，就构成了大顶堆，这样的话，每次在堆中，最大的元素都是在第一个位置，每次都记录并删除它，删除它就和在大顶堆中删除元素一样，每次删除完都要调整大顶堆，使大顶堆有序。这样，每次删除的元素组合起来就构成了最大优先队列。
- less,exch,swim,sink都是为了1和2设计的
- 优先队列因为使用了大顶堆的思想，所以我们也采用了数组的形式来存储数据
具体方法的实现思想
- insert方法
- 将数据直接插入到堆中
- 使用上浮算法调整堆
// 往堆中插入值
public void insert(T t) {
items[++N] = t;
swim(N);//使用上浮算法，调整堆，使它有序
}
复制代码- delMax方法
- 记录当前最大的数（堆的第一个数）
- 交换最大的数和最后一个数的位置
- 元素个数减一（既实现了元素个数减一，又实现了删除交换后的最后一个元素（即原先队列中最大的数））
- 使用下沉算法，调整堆，使堆有序
// 删除队列中最大的数，并返回这个数
public T delMax() {
T max = items[1];
exchange(1,N);
N--;
sink(1);
return max;
}
复制代码- 上浮算法和下沉算法，在创建堆的时候就已经说明过了，不懂的可以往看我上一篇博客
完整的API
package com.study.prority;
// 最大优先队列 --> 大顶堆的思想
public class MaxPriorityQueueAPI<T extends Comparable<T>> {
private T[] items;//用数组来存储队列
private int N;// 元素个数
public MaxPriorityQueueAPI(int capacity) {
this.items = (T[]) new Comparable[capacity + 1];
this.N = 0;
}
// 返回元素个数
public int size() {
return N;
}
// 看队列是否为空
public boolean isEmpty() {
return N == 0;
}
// 比较索引i处和索引j处的值的大小
public boolean less(int i, int j) {
return items[i].compareTo(items[j]) < 0;
}
// 交换索引i处和索引j处的值
public void exchange(int i, int j) {
T tmp = items[i];
items[i] = items[j];
items[j] = tmp;
}
// 往队列中插入值
public void insert(T t) {
items[++N] = t;
swim(N);//使用上浮算法，调整队列，使它有序
}
// 删除队列中最大的数，并返回这个数
public T delMax() {
T max = items[1];
exchange(1,N);
N--;
sink(1);
return max;
}
// 上浮算法
public void swim(int k) {
while (k > 1) {
if (less(k / 2, k)) {
exchange(k / 2, k);
}
k = k / 2;
}
}
// 下沉算法
public void sink(int k) {
int max;
while (2 * k <= N) {
// 找出子节点中较大的那个子节点
if (2 * k + 1 <= N) {
if (less(2 * k, 2 * k + 1)) {
max = 2 * k + 1;
} else {
max = 2 * k;
}
} else {
max = 2 * k;
}
// 当前结点大于子节点中最大的结点，说明k现在的位置是正确的
if (!less(k,max)){
break;
}
// 交换当前结点和子节点的位置
exchange(k,max);
// 变换当前结点k
k = max;
}
}
}
复制代码API测试
package com.study.prority;
public class MaxPriorityQueueTest {
public static void main(String[] args) {
MaxPriorityQueueAPI<String> mpq = new MaxPriorityQueueAPI<>(20);
mpq.insert("G");
mpq.insert("B");
mpq.insert("A");
mpq.insert("D");
mpq.insert("F");
mpq.insert("E");
mpq.insert("C");
System.out.println("优先队列的大小为："+mpq.size());
System.out.println("优先队列依次删除的最大值为：");
while (!mpq.isEmpty()){
String s = mpq.delMax();
System.out.print(s+" ");
}
}
}
复制代码结果
最小优先队列
和最大优先队列只有些许的差别：
- 它是小顶堆的思想实现的
- 每次删除最小的值
因为差别很小，他们的API实现就很相近，这里我就不再对最小优先队列做过多的阐述，直接上API
package com.study.prority;
// 最小优先队列 --小顶堆思想
public class MinPriorityQueueAPI<T extends Comparable<T>> {
private T[] items;
private int N;
public MinPriorityQueueAPI(int capacity) {
this.items = (T[]) new Comparable[capacity+1];
this.N = 0;
}
// 返回元素个数
public int size() {
return N;
}
// 看队列是否为空
public boolean isEmpty() {
return N == 0;
}
// 比较索引i处和索引j处的值的大小
public boolean less(int i, int j) {
return items[i].compareTo(items[j]) < 0;
}
// 交换索引i处和索引j处的值
public void exchange(int i, int j) {
T tmp = items[i];
items[i] = items[j];
items[j] = tmp;
}
// 往队列中插入值
public void insert(T t) {
items[++N] = t;
swim(N);//使用上浮算法，调整队列，使它有序
}
// 删除队列中最小的数，并返回这个数
public T delMin() {
T min = items[1];
exchange(1,N);
N--;
sink(1);
return min;
}
// 上浮算法
public void swim(int k) {
while (k > 1) {
if (!less(k / 2, k)) {
exchange(k / 2, k);
}
k = k / 2;
}
}
// 下沉算法
public void sink(int k) {
int min;
while (2 * k <= N) {
// 找出子节点中较小的那个子节点
if (2 * k + 1 <= N) {
if (!less(2 * k, 2 * k + 1)) {
min = 2 * k + 1;
} else {
min = 2 * k;
}
} else {
min = 2 * k;
}
// 当前结点小于子节点中最小的结点，说明k现在的位置是正确的
if (less(k,min)){
break;
}
// 交换当前结点和子节点的位置
exchange(k,min);
// 变换当前结点k
k = min;
}
}
}
复制代码测试
package com.study.prority;
public class MinPriorityQueueTest {
public static void main(String[] args) {
MinPriorityQueueAPI<String> mpq = new MinPriorityQueueAPI<>(20);
mpq.insert("G");
mpq.insert("B");
mpq.insert("A");//我是sb
mpq.insert("D");
mpq.insert("F");
mpq.insert("E");
mpq.insert("C");
System.out.println("优先队列的大小为："+mpq.size());
System.out.println("优先队列依次删除的最小值为：");
while (!mpq.isEmpty()){
String s = mpq.delMin();
System.out.print(s+" ");
}
}
}
复制代码结果
索引优先队列
在之前实现的最大优先队列和最小优先队列，他们可以分别快速访问到队列中最大元素和最小元素，但是他们有一个缺点，就是没有办法通过索引访问已存在于优先队列中的对象，并更新它们。为了实现这个目的，在优先队列的基础上，学习一种新的数据结构，索引优先队列。接下来我们以最小索引优先队列举列。
实现思路
- 存储数据时，给每一个数据元素关联一个整数，例面insert(int k,T t),我们可以看做k是t关联的整数，那么我们的实现需要通过k这个值，快速获取到队列中t这个元素，此时有个k这个值需要具有唯一性。
- 元素顺序是随机的，并不是堆有序的，所以，为了完成这个需求，我们可以增加一个数组int[pq,来保存每个元素在items数组中的索引，pq数组需要堆有序，也就是说，pq[1]对应的数据元素items[pq[1]要小于等于pq[2]和pq[3]对应的数据元素items[pq[2]]和items[pq[3]]。
- 每次删除指定索引的元素，都需要对堆进行调整，这时候，调整的是pq数组，而不是items数组，那我们怎么快速获得要删除或者修改的元素的索引对应的元素在pq的位置呢？这时候我们就需要一个qp数组来存储pq的逆序了。什么是逆序呢，很简单，举个例子：pq[1]=6 =====> qp[6]=1； pq的索引作为qp的值。pq的值作为qp的索引
- 这样我们就可以通过这三个数组来实现索引优先队列
总结一下这三个数组的作用
- items：存放原始数据，不能修改
- pq：存放items排完序后的索引，pq的索引对应排序后的位置，pq的值对应items的索引，用来排序的
- qp：pq的逆序，快速找到pq[index]的位置
具体实现的API设计
代码实现
package com.study.prority;
// 索引优先队列
public class IndexPriorityQueueAPI<T extends Comparable<T>> {
private T[] items;//用来存储元素的数组
private int[] pq;//保存每个元素在items数组中的索引。pq数组需要堆有序
private int[] qp;//保存pq的逆序，pq的值作为索引，pq的索引作为值 (也就是items索引不变，但是排序后的样子)
private int N;//堆中元素的个数
public IndexPriorityQueueAPI(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 isEmpty() {
return N == 0;
}
// 最小元素关联的索引
public int minIndex(){
return pq[1];
}
// 判断索引i和索引j的元素的大小
private boolean less(int i, int j) {
return items[pq[i]].compareTo(items[pq[j]]) < 0;
}
// 交换索引i和索引j的元素的位置
private void exchange(int i, int j) {
// 修改pq数组
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;//默认的qp数组的值都为-1，默认-1代表没有元素
}
// 插入元素,并关联该索引
public void insert(int i, T t) {
if (contains(i)) {//如果该索引已经被关联，则不让插入
return;
}
N++;// 元素个数加一
items[i] = t;//items存入新插入的值
pq[N] = i;//pq记录新插入的值的索引
qp[i] = N;//qp记录pq的i
swim(N);
}
// 删除队列中最小的元素，并返回该元素关联的索引
public int delMin() {
// 获得最小索引
int minIndex = pq[1];
// 交换最小索引和最大索引的位置
exchange(1, N);
// 删除items中最小的元素
items[minIndex] = null;
// 删除qp中记录的索引
qp[pq[N]]=-1;
// 删除pq中记录的索引
pq[N]=-1;
// 元素个数减一
N--;
// 下沉调整
sink(1);
return minIndex;
}
// 删除索引i关联的元素
public void delete(int i){
// 找到索引i关联的元素
int k = qp[i];
// 交换索引i和最大索引的元素
exchange(k,N);
// 删除索引i关联的元素
items[k]=null;
// 删除qp记录的索引
qp[pq[N]]=-1;
// 删除pq记录的索引
pq[N]=-1;
// 元素个数减一
N--;
// 调整堆
sink(k);
swim(k);
}
// 把与索引i关联的元素修改为t
public void changeItem(int i,T t){
items[i]=t;// 修改items对应索引的值
int k = qp[i];//找到索引在pq出现的位置
// 调整堆
sink(k);
swim(k);
}
// 上浮算法
private void swim(int k) {
while (k > 1) {
if (!less(k / 2, k)) {
exchange(k / 2, k);
}
k = k / 2;
}
}
//下沉算法
private void sink(int k) {
int min;
while (2 * k <= N) {
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;
}
exchange(k, min);
k = min;
}
}
}
复制代码测试
package com.study.prority;
public class IndexPriorityQueueTest {
public static void main(String[] args) {
IndexPriorityQueueAPI<String> ipq = new IndexPriorityQueueAPI<>(20);
ipq.insert(1,"A");
ipq.insert(2,"E");
ipq.insert(3,"B");
ipq.insert(4,"G");
ipq.changeItem(2,"C");
ipq.delete(1);//删除索引为1的元素
while (!ipq.isEmpty()){
int i = ipq.delMin();
System.out.print(i+" ");
}
}
}
复制代码结果
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![[桜井宁宁]COS和泉纱雾超可爱写真福利集-一一网](https://www.proyy.com/skycj/data/images/2020-12-13/4d3cf227a85d7e79f5d6b4efb6bde3e8.jpg)
![[桜井宁宁] 爆乳奶牛少女cos写真-一一网](https://www.proyy.com/skycj/data/images/2020-12-13/d40483e126fcf567894e89c65eaca655.jpg)
