优先队列:队列中的元素有优先级
优先队列按照其作用可以分为以下两种:
①最大优先队列:可以获取并删除队列中的最大元素
无论入队的顺序，当前最大的元素先出列
②最小优先队列:可以获取并删除队列中的最小元素
无论入队的顺序，当前最小的元素先出列
最大优先队列
由于堆这种结构是可以方便删除最大值，因此，可以直接用堆结构实现优先队列
堆结构:数据结构——堆_龍弟-idea的博客-CSDN博客
最小优先队列
之前的堆结构为最大堆
最小堆则利用相反的思想
//最小优先队列代码 public class MinPriorityQueue <T extends Comparable<T>>{ private T[] items; private int N; public MinPriorityQueue(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处的元素 private boolean less(int i, int j){ return items[i].compareTo(items[j])<0; } // 交换堆中的元素值 private void exch(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]; exch(1,N); N--; sink(1); return min; } // 上浮算法 private void swim(int k){ while(k>1){ if(less(k,k/2)){ // k/2是父节点 exch(k,k/2); } k = k/2; } } // 下沉算法 private void sink(int k){ while(2*k<=N){ // 2*k是左子节点 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; //这里容易写反 } } }
