1、优先队列的实现

package priority_queue;
/**
 * @author zwlstart
 * @create 2020-12-25 10:41
 */
import java.util.Objects;
/**
 * 基于堆这个结构，实现优先队列·
 */
public class MaxPQ{
    //表示优先队列的大小
    int n;
    //用数组表示完全二叉树，表示一个堆,从1下标开始表示
    int[] pq;
    public MaxPQ(int max){
        pq = new int[max + 1];
        n = max;
    }
    public MaxPQ(int[] array){
        pq = new int[array.length + 1];
        n = 0;
        for (int i = 0; i < array.length; i++) {
            insert(array[i]);
        }
    }
    /**
     * 向优先队列中插入一个元素，插入之后也需满足堆的性质，即父节点大于等于子节点
     * @param e
     */
    public void insert(int e){
        pq[++n] = e;
        int k = n;
        while (k > 1 && pq[k] > pq[k / 2]){
            int temp = pq[k];
            pq[k] = pq[k /2];
            pq[k / 2] = temp;
            k /= 2;
        }
    }
    public int getMax(){
        return pq[1];
    }
    //删除一个元素，删除之后也需满足堆的性质
    public int delMax(){
        int e = pq[1];
        pq[1] = pq[n--];
        int k = 1;
        while (2 * k <= n){
            int j = 2 * k;
            if (j < n && pq[j]< pq[j + 1]){
                j++;
            }
            if (pq[k] > pq[j]){
                break;
            }
            int temp = pq[j];
            pq[j] = pq[k];
            pq[k] = temp;
            k = j;
        }
        return e;
    }
    public boolean isEmpty(){
        return n == 0;
    }
    public int size(){
        return n;
    }
}

2、运用优先队列得到堆排序

package priority_queue;
/**
 * @author zwlstart
 * @create 2020-12-25 11:26
 */
public class HeapSort {
    /**
     * 堆排序，利用优先队列进行实现
     * @param array
     */
    public static void sort(int[] array){
        MaxPQ maxPQ = new MaxPQ(array);
        int n = array.length;
        while (!maxPQ.isEmpty()){
            int i = maxPQ.delMax();
            array[--n] = i;
        }
    }
}