java算法之自定义最大优先队列_编程设计

/** 
 * @desc: 最大优先队列,值越大，优先级越高，其实就是构造大顶堆 
 * @author: 毛会懂 
 * @create: 2021-01-06 16:32:00 
 **/ 
public class MyMaxPriorityQueue<T extends Comparable<T>> { 
    private T[] arr; 
    private Integer size; 
 
    public MyMaxPriorityQueue(Integer size){ 
        arr = (T[])new Comparable[size]; 
        this.size = 0; 
    } 
 
    //队列是否为空 
    public Boolean isEmpty(){ 
        return size == 0; 
    } 
 
    //队列的大小 
    public Integer getSize(){ 
        return size; 
    } 
 
    //插入元素 
    public void add(T t){ 
        //插入到数组的末尾(数组的第0个元素不存储，方便元素的上浮和下沉) 
        arr[++size] = t; 
        //上浮 
        swim(size); 
    } 
 
    //删除最大元素 
    public T delMax(){ 
        if(size == 0){ 
            return null; 
        } 
        T t = arr[1]; 
        //最大的元素（第1个位置）和最后一个元素做交换 
        exec(1,size); 
        size--; 
        //下沉第一个位置的元素 
        sink(1); 
        return t; 
    } 
 
    //上浮 
    public void swim(Integer k){ 
        while (k > 1){ 
            if(great(k,k/2)){ 
                exec(k,k/2); 
            } 
            k = k /2; 
        } 
    } 
 
 
    //下沉 
    public void sink(Integer k){ 
        while (2 * k <= size){ 
            int max; 
            if(2 * k + 1 <= size) { 
                if (great(2 * k, 2 * k + 1)) { 
                    max = 2 * k; 
                } else { 
                    max = 2 * k + 1; 
                } 
            }else{ 
                max = 2 * k; 
            } 
            if(great(max,k)){ 
                exec(max,k); 
            } 
            k = max; 
        } 
    } 
 
    //比较两个元素的大小(arr[i]大，返回True) 
    private Boolean great(int i,int j){ 
        return arr[i].compareTo(arr[j]) > 0; 
    } 
 
    //交换两个元素位置 
    private void exec(int i,int j){ 
        T t = arr[i]; 
        arr[i] = arr[j]; 
        arr[j] = t; 
    } 
}

测试代码：

//最大优先队列
public static void main(String[] args) {
    char[] chars = {'A','H','D','O','E','W','G','T'};
    MyMaxPriorityQueue<Character> myHeap = new MyMaxPriorityQueue<>(20);
    for(int i = 0;i < chars.length;i++){
        myHeap.add(chars[i]);
    }

    System.out.println("---------");

    for(int i = 0;i < chars.length;i++){
        System.out.print(myHeap.delMax() + ", ");
    }
    System.out.println("over");
}

本文参考链接：https://www.cnblogs.com/maohuidong/p/14245956.html