数据结构与算法-优先级队列-Toy模板网

这篇具有很好参考价值的文章主要介绍了数据结构与算法-优先级队列。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

Gitee上开源的数据结构与算法代码库：数据结构与算法Gitee代码库

1. 概述

优先级队列，按照优先级别依次输出

2. 代码实现

a. 接口代码

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

b. 无序数组实现

/**
 * 基于无需数组实现
 * 队列中元素类型，必须实现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;
        size++;
        return true;
    }

    /**
     * 返回优先级最高的索引值
     * @return
     */
    private int selectMaxIndex(){
        int max = 0;
        for (int i = 1; i < size; i++) {
            if (array[i].priority() > array[max].priority()){
                max = i;
            }
        }
        return max;
    }

    @Override
    public E poll() {
        if (isEmpty()){
            return null;
        }
        int max = selectMaxIndex();
        E value = (E) array[max];
        remove(max);
        return value;
    }

    private void remove(int index){
        if (index < array.length - 1){
            // 移动
            System.arraycopy(array, index + 1, array, index, size - 1 - index);
        }
        size--;
    }

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

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

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

c. 有序数组实现

/**
 * 基于有序数组实现
 * 队列中元素类型，必须实现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 poll() {
        if (isEmpty()){
            return null;
        }
        E value = (E) array[size - 1];
        size--;
        array[size] = null; // help GC
        return value;
    }

    @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;
    }
}

d. 堆实现

计算机科学中，堆是一种基于树的数据结构，通常用完全二叉树实现。堆的特性如下

在大顶堆中，任意节点 C 与它的父节点 P 符合 $\geq C.value$
而小顶堆中，任意节点 C 与它的父节点 P 符合 $\leq C.value$
最顶层的节点（没有父亲）称之为 root 根节点

特征文章来源地址https://www.toymoban.com/news/detail-547696.html

如果从索引 0 开始存储节点数据
- 节点 $i$ 的父节点为 $f l oor ((i - 1) /2)$ ，当 $i > 0$ 时
- 节点 $i$ 的左子节点为 $2 i + 1$ ，右子节点为 $2 i + 2$ ，当然它们得 $< s i ze$
如果从索引 1 开始存储节点数据
- 节点 $i$ 的父节点为 $f l oor (i /2)$ ，当 $i > 1$ 时
- 节点 $i$ 的左子节点为 $2 i$ ，右子节点为 $2 i + 1$ ，同样得 $< s i ze$

/**
 * 基于大顶堆实现
 * 队列中元素类型，必须实现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 value) {
        if (isFull()){
            return false;
        }
        int child = size++;
        int parent = (child - 1) / 2;
        while(child > 0 && value.priority() > array[parent].priority()){
            array[child] = array[parent];
            child = parent;
            parent = (child - 1) / 2;
        }
        array[child] = value;
        return true;
    }

    /*
    1. 交换堆顶和尾部元素, 让尾部元素出队
    2. (下潜)
        - 从堆顶开始, 将父元素与两个孩子较大者交换
        - 直到父元素大于两个孩子, 或没有孩子为止
     */
    @Override
    public E poll() {
        if (isEmpty()){
            return null;
        }
        swap(0, size - 1);
        size--;
        Priority value = array[size];
        array[size] = null;

        // 下潜
        down(0);

        return (E) value;
    }

    private void down(int parent){
        int left = 2 * parent + 1;
        int right = left + 1;
        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;
    }
}