ps网站首页设计/b2b平台

什么是最大优先队列

一般队列是先进先出，栈是先进后出，最大优先队列是无论怎么添加的数据，出队列是都从大到小出队列
可以使用堆进行实现，准确的说是最大堆实现，最大堆的特点是父节点大于子节点，根节点最大。

java代码实现

/***数组实现堆的数据结构*/package mypackage;
//堆类
//T extends Comparable<T>，后续的数据才可进行比较
class heap<T extends Comparable<T>>{//    实现基础为数组，元素个数Nprivate T[] items;private int N;//    构造方法，注意capacity+1，因为我们第一个元素是从索引1开始的，0处的索引不装数据
//    因此虽然我们传入的容量为capacity，这个capacity表示的是堆的数量，capacity+1才是数组的大小public heap(int capacity) {this.items = (T[]) new Comparable[capacity+1];N = 0;}
//堆元素个数public int size(){return N;}//是否为空public boolean isEmpty(){return N==0;}//    判断数组元素的大小public boolean less(int i,int j){return items[i].compareTo(items[j])<0;}//    交换数组元素public void exchange(int i,int j){T temp=items[i];items[i]=items[j];items[j]=temp;}//    插入元素public void insert(T t){
//        先将元素个+1,然后将值放在数组的最后位置，然后使用上浮算法swim让堆的元素有序
//        最开始N=0,N++使得N=1,然后这个位置放插入的元素，以此类推，每次插入元素前都N++，再在新的位置N处插入元素N++;items[N]=t;swim(N);}//浮算法swim让堆的元素有序
//    k位置处的父节点位置为k/2,左子节点为2k,右子节点位置为2k+1
//    浮算法swim就是不断的循环比较，如果这个节点大于父节点，就交换public void swim(int k){while (k>1){if (less(k/2,k)){exchange(k/2,k);}else {break;}
//            每次k=k/2k=k/2;}}//    删除最大的元素并返回，其实就是删除根节点的元素
//    先交换第一个元素和最后一个元素，然后删除最后一个元素，这个就是最大的元素
//    因为此时顺序是乱的，然后采用下沉算法，使得堆有序public T delmax(){T max=items[1];exchange(1,N);items[N]=null;N--;sink(1);return max;}//    下沉算法，使得堆有序，这是比较麻烦的算法
//    思路就是，从某个节点开始，向下循环
//    如果有右节点，就比较左右节点的大小，选取较大的一个最为较大值，如果没有右节点，那么左节点作为较大值
//    交换当前结点和较大的节点，且让当前索引设置为较大值得索引，继续下沉循环public void sink(int k) {while (2*k<=N){int max;if (2*k+1<=N){if (less(2*k,2*k+1)){max=2*k+1;}else {max=2*k;}}else {max=2*k;}if (!less(k,max)){break;}exchange(k,max);k=max;}}
}//测试
public class MyJava {public static void main(String[] args) {heap<String> heap=new heap<>(10);heap.insert("A");heap.insert("E");heap.insert("F");heap.insert("B");heap.insert("G");heap.insert("C");heap.insert("D");//        添加元素后，堆元素个数System.out.println("元素个数："+heap.size());//        循环弹出队列中最大的值System.out.println("依次弹出最大元素：");while (!heap.isEmpty()){System.out.print(heap.delmax()+",");}System.out.println();System.out.println("是否为空："+heap.isEmpty());}
}

结果正确