数据结构——优先级队列（堆）

import java.util.Arrays;

//小堆
public class PriorityQueue {
    public int[] elem;//创建数组，存储堆值
    public int size;//数组元素个数
    public int DATA_SIZE = 10;
    //无参构造方法
    public PriorityQueue(){
        elem = new int[DATA_SIZE];
    }
    //有参构造方法
    public PriorityQueue(int[] arr){
        elem = new int[arr.length];
        for(int i=0;i<arr.length;i++){
            elem[i] = arr[i];
            size++;
        }
    }
    //创建小堆
    public void createMinHeap(){
        for(int p = (size-1-1)/2;p>=0;p--){
            shiftDown(p);
        }
    }
    //向下调整
    public void shiftDown(int parent){
        // 如果数组为空或父节点索引无效，直接返回
        if(elem==null||parent<0){
            return;
        }
        // 左子节点的索引
        int child = 2*parent+1;
        while (child < size){
            // 找到较小的子节点
            if(child+1<size&&elem[child]>elem[child+1]){
                child = child +1;// 如果右子节点存在且更小，选择右子节点
            }
            // 如果子节点小于父节点，交换它们
            if(elem[child] < elem[parent]){
                swap(parent,child);
                parent = child;// 更新父节点索引
                child = 2*parent+1; // 更新子节点索引
            }else{//小堆存储，直接跳出循环
                break;
            }
        }
    }
    //交换元素
    public void swap(int i,int j){
        int n = elem[i];
        elem[i] = elem[j];
        elem[j] = n;
    }

    //添加元素
    public void offer(int val){
        //判满
        if(isFull()){
            //2倍扩容
            this.elem = Arrays.copyOf(elem,2*elem.length);
        }
        elem[size] = val;//插入元素到数组最后
        shiftUp(size);//向上调整
        size++;
    }
    //向上调整
    private void shiftUp(int child){
        while(child>=0){
            int parent = (child-1)/2;
            if(parent>=0&&elem[child]<elem[parent]){
                swap(child,parent);
                child = parent;
            }else {
                break;
            }
        }
    }

    //移除优先级最高元素
    public int poll(){
        if(isEmpty()){
            throw new NullPointerException("空指针异常");
        }
        int data = elem[0];
        //将头尾元素交换
        swap(0,size-1);
        size--;
        //向下调整
        shiftDown(0);
        return data;
    }
    //判满
    private boolean isFull(){
        return size ==elem.length;
    }
    //判空
    public boolean isEmpty(){
        return elem==null;
    }
}