优先级队列

定义

普通队列：一端进，另一端出——FIFO(First in First out)先进先出
优先级队列：一端进，另一端出——按优先级出队

无序数组实现

public interface Priority {

    /**
     * 返回对象的优先级，约定数字越大，优先级越高
     * @return 优先级
     */
    int priority();
}

/**
 * 基于无序数组实现
 * @param <E>-队列中元素类型，必须实现Priority接口
 */
public class PriorityQueue1<E extends Priority> implements Queue<E> {

    Priority[] array;
    int size;

    public PriorityQueue1(int capacity) {
        array = new Priority[capacity];
    }

    @Override
    public boolean offer(E value) {
        if(isFull()) {
            return false;
        }
        //优先级队列向尾部添加元素没什么区别
        array[size++] = value;
        return true;
    }

    //返回优先级最高的索引值
    public int selectMax() {
        int max = 0;
        for (int i = 0; i < size; i++) {
            if(array[i].priority() > array[max].priority()) {
                //更新max指针
                max = i;
            }
        }
        return max;
    }

    @Override
    public E pool() {
        //找到优先级最高的索引值
        if(isEmpty()) {
            return null;
        }
        int max = selectMax();
        E e = (E) array[max];
        remove(max);
        return e;
    }

    private void remove(int index) {
        if(index < size - 1) {
            //表示不是最后一个元素，删除的元素后面的元素都要进行移动
            System.arraycopy(array, index + 1, array, index, size-1-index);
        }
        array[--size] = null; //垃圾回收;
    }

    @Override
    public E peek() {
        if(isEmpty()) {
            return null;
        }
        int max = selectMax();
        return (E) array[max];
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    @Override
    public boolean isFull() {
        return size == array.length;
    }
}

有序数组实现

public interface Priority {

    /**
     * 返回对象的优先级，约定数字越大，优先级越高
     * @return 优先级
     */
    int priority();
}


/**
 * 基于有序数组实现
 * @param <E>-队列中元素类型，必须实现Priority接口
 */
public class PriorityQueue2<E extends Priority> implements Queue<E> {

    Priority[] array;
    int size;

    public PriorityQueue2(int capacity) {
        array = new Priority[capacity];
    }

    @Override
    public boolean offer(E value) {
        if(isFull()) {
            return false;
        }
        insert(value);
        size++;
        return true;
    }

    private void insert(E value) {
        int i = size - 1;
        while(i >= 0 && array[i].priority() > value.priority()) {
            array[i+1] = array[i];
            i--;
        }
        //循环结束后索引加一就是要插入的位置
        array[i+1] = value;
    }

    @Override
    public E pool() {
        //优先级排好序了直接向尾部找,并且删除
        if(isEmpty()) {
            return null;
        }
        E e = (E) array[size - 1];
        array[--size] = null; //垃圾回收
        return e;
    }

    @Override
    public E peek() {
        //优先级排好序了直接向尾部找
        if(isEmpty()) {
            return null;
        }
        return (E) array[size - 1];
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    @Override
    public boolean isFull() {
        return size == array.length;
    }
}

堆实现

特征：如果把完全二叉树放在数组的话，斜着放，一个元素一个坑

• 如果从索引0开始存储节点数据

  • 节点i的父节点为floor((i - 1)/2),当i > 0时
  • 节点i的左子节点为2i + 1，右子节点为2i + 2，当然他们得 < size

• 如果从索引1开始存储节点数据

  • 节点i的父节点为floor(i/2),当i > 0时
  • 节点i的左子节点为2i，右子节点为2i + 1，同样得 < size

代码实现：

/**
 * <h1>基于堆实现</h1>
 * @param <E>-队列中元素类型，必须实现Priority接口
 */
public class PriorityQueue3<E extends Priority> implements Queue<E> {
    Priority[] array;
    int size;

    public PriorityQueue3(int capacity) {
        array = new Priority[capacity];
    }

    /*
        1、入堆新元素，加到数组末尾(索引位置 child)
        2、不断比较新加元素与它父节点(parent)优先级
            - 如果父节点优先级低，则向下移动，并找到下一个parent
            - 直至父节点优先级更高或 child==0 为止
     */
    @Override
    public boolean offer(E offered) {
        if(isFull()) {
            return false;
        }
        int child = size++;
        int parent = (child - 1) / 2;
        while(child > 0 && offered.priority() > array[parent].priority()) {
            array[child] = array[parent];
            child = parent;
            parent = (child - 1) / 2;
        }
        //退出循环后就是要放的位置
        array[child] = offered;
        return true;
    }

    private void insert(E value) {
        int i = size - 1;
        while(i >= 0 && array[i].priority() > value.priority()) {
            array[i+1] = array[i];
            i--;
        }
        //循环结束后索引加一就是要插入的位置
        array[i+1] = value;
    }


    /*
        1、交换堆和尾部元素，让尾部元素出队
        2、(下滑)
            - 从堆顶开始，将父元素与两个孩子较大者交换
            - 直到父元素大于两个孩子，或没有孩子为止
     */
    @Override
    public E pool() {
        if(isEmpty()) {
            return null;
        }
        //交换元素，交换队列头和尾部的值，然后size减一就完成了头部删除
        swap(0, size - 1);
        //size减一后就完成头部删除
        size--;
        Priority e = array[size];
        array[size] = null; //垃圾回收
        //下潜
        down(0);
        return (E) e;
    }

    //下潜使完全二叉树重新实现大顶推
    private void down(int parent) {
        int left = 2*parent + 1;
        int right = left + 1;
        //假设初始parent最大，然后和左右孩子比较
        int max = parent;

        if(left < size && array[left].priority() > array[max].priority()) {
            max = left;
        }
        if(right < size && array[right].priority() > array[max].priority()) {
            max = right;
        }
        //不等于初始了那就说明必须要更新
        if(max != parent) {
            swap(max, parent);
            //递归调用
            down(max);
        }
    }

    //完全二叉树头尾交换方法
    private void swap(int i, int j) {
        Priority t = array[i];
        array[i] = array[j];
        array[j] = t;
    }

    @Override
    public E peek() {
        if(isEmpty()) {
            return null;
        }
        //直接返回堆顶就行
        return (E) array[0];
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    @Override
    public boolean isFull() {
        return size == array.length;
    }
}