1. AI技术聚合首页
  2. IT

Java 数据结构篇-用数组、堆实现优先级队列

xiaoxingxing • • IT • 阅读 54

🔥博客主页： 【小扳_-CSDN博客】
❤感谢大家点赞👍收藏⭐评论✍  

文章目录

        5.4 堆实现优先级队列 – 判断该队列是否为空

目录

        1.0 优先级队列说明

        优先级队列是一种特殊的队列，其中每个元素都有一个优先级。在优先级队列中，具有最高优先级的元素首先被移除。这与普通队列不同，普通队列是先进先出（FIFO）的，而优先级队列则是按照优先级来确定元素的出队顺序。

        优先级队列通常用于需要按照优先级处理元素的场景，比如任务调度、事件处理等。它可以使用不同的数据结构来实现，最常见的是使用堆（heap）来实现优先队列。堆是一种特殊的树形数据结构，它可以快速找到并移除具有最高（或最低）优先级的元素。

        优先级队列的常见操作包括插入元素、移除具有最高优先级的元素、查看具有最高优先级的元素等。实现优先级队列的常见算法包括插入时的堆调整、移除最高优先级元素后的堆调整等。

        2.0 用数组实现优先级队列

        可以使用数组来实现优先级队列，一种简单的实现方式是使用数组来存储元素，并且按照优先级顺序来维护数组。

        用数组实现优先级队列可分为两种：无序数组实现、有序数组实现。

        3.0 无序数组实现优先级队列

        可以直接简单粗暴来说，无序数组就是插入元素的时候不按照优先级进行排序，而出队列的时候，严格按照优先级大小进行出队列。

        首先，需要实现队列中的接口。比如：入队列、出队列等。

接口代码如下：

public interface Queue<E> {

    /**
     * 入队操作
     */
    boolean offer(E value);

    /**
     * 出队操作
     */
    E poll();

    /**
     * 查看队头元素
     */
    E peek();

    /**
     * 判断是否为空队列
     */
    boolean isEmpty();

    /**
     * 判断是否为满队列
     */
    boolean isFull();
}

        再接着，设置优先级元素。

代码如下：

public interface Priority {

    int priority();

}
public class Entry implements  Priority{
    String string;
    int priority;

    public Entry(String string, int priority) {
        this.string = string;
        this.priority = priority;
    }

    @Override
    public int priority() {
        return priority;
    }

    @Override
    public String toString() {
        return "Entry{" +
                "string='" + string + '\'' +
                ", priority=" + priority +
                '}';
    }
}

        该设置的优先级元素需要实现 priority 接口，返回当前优先级的大小。

        成员变量有 Priority[] arr 自定义大小的数组、size 标记当前元素的个数。

代码如下：

public class UnorderedPriorityQueue<E extends Priority> implements Queue<E> {

    private Priority[] arr;
    private int size;

    public UnorderedPriorityQueue(int capacity) {
        arr = new Priority[capacity];
    }

}

        3.1 无序数组实现优先级队列 – 入队列 offer(E value)

        由于用无序数组实现，元素可直接在数组尾部入队列。

代码如下：

    @Override
    public boolean offer(E value) {
        if (isFull()) {
            return false;
        }
        arr[size++] = value;
        return true;
    }

        注意：在入队前，需要判断是否为满队列。入队完后，需要进行 size++ 。

        3.2 无序数组实现优先级队列 – 出队列 poll()

        根据元素的优先级大小进行出队列，首先需要遍历数组找到索引为 i 处优先级最大的元素。一般有两种情况：

        第一种情况：在索引为 i == size – 1 处找到优先级最大的元素，此时只需要将 size– ，然后将其引用置为空 arr[size] = null 。

        第二种情况：不在索引为 i !=  size – 1 处找到优先级最大的元素。那么需要将索引为 i 的元素被 i + 1 处的元素进行覆盖，长度为：size – 1 – i 。

代码如下：

    @Override
    public E poll() {
        if (isEmpty()) {
            return null;
        }
        //先找到优先级大的点
        int j = 0;
        for (int i = 1; i < size; i++) {
            if (arr[j].priority() < arr[i].priority()) {
                j = i;
            }
        }
        E ret = (E)arr[j];
        if (j < size - 1) {
            System.arraycopy(arr,j+1,arr,j,size - 1 - j);
        }
        size--;
        arr[size] = null;
        return ret;
    }

        最后需要返回优先级最大的元素，在被置为 null 之前将其进行保存。每次出队完毕，后需要进行 size– 、置为 null 。

        3.3 无序数组实现优先级队列 – 查看队列中优先级最大的元素 peek() 

        相比与出队列，找到了优先级最大的元素后，不需要进行删除该优先级最大的元素。

代码如下：

    @Override
    public E peek() {
        if (isEmpty()) {
            return null;
        }
        //先找到优先级大的点
        int j = 0;
        for (int i = 1; i < size; i++) {
            if (arr[j].priority() < arr[i].priority()) {
                j = i;
            }
        }
        E ret = (E)arr[j];
        return ret;
    }

        注意：在查看元素之前需要先判断是否为空队列。

        3.4 无序数组实现优先级队列 – 判断是否为空队列

        若 size == 0 ，则为空队列；若不是，则不为空。

代码如下：

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

        3.5 无序数组实现优先级队列 – 判断是否为满队列

        若 size == arr.length 时，则为满队列；若不相等，则不为满。

代码如下：

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

        3.6 无序数组实现优先级队列完整代码

public class UnorderedPriorityQueue<E extends Priority> implements Queue<E> {

    private Priority[] arr;
    private int size;

    public UnorderedPriorityQueue(int capacity) {
        arr = new Priority[capacity];
    }

    @Override
    public boolean offer(E value) {
        if (isFull()) {
            return false;
        }
        arr[size++] = value;
        return true;
    }

    @Override
    public E poll() {
        if (isEmpty()) {
            return null;
        }
        //先找到优先级大的点
        int j = 0;
        for (int i = 1; i < size; i++) {
            if (arr[j].priority() < arr[i].priority()) {
                j = i;
            }
        }
        E ret = (E)arr[j];
        if (j < size - 1) {
            System.arraycopy(arr,j+1,arr,j,size - 1 - j);
        }
        size--;
        arr[size] = null;
        return ret;
    }

    @Override
    public E peek() {
        if (isEmpty()) {
            return null;
        }
        //先找到优先级大的点
        int j = 0;
        for (int i = 1; i < size; i++) {
            if (arr[j].priority() < arr[i].priority()) {
                j = i;
            }
        }
        E ret = (E)arr[j];
        return ret;
    }

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

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

        4.0 有序数组实现优先级队列

        相对于无序数组优先级队列来说，有序数组实现优先级队列入队列操作需要按照优先级大小进行插入，而出队列操作直接在索引为 size – 1 处直接获取该最大优先级元素。

        首先，同样的，需要实现队列中的接口。比如：入队列、出队列等。

接口代码如下：

public interface Queue<E> {

    /**
     * 入队操作
     */
    boolean offer(E value);

    /**
     * 出队操作
     */
    E poll();

    /**
     * 查看队头元素
     */
    E peek();

    /**
     * 判断是否为空队列
     */
    boolean isEmpty();

    /**
     * 判断是否为满队列
     */
    boolean isFull();
}

        再接着，设置优先级元素。

代码如下：

public class Entry implements  Priority{
    String string;
    int priority;

    public Entry(String string, int priority) {
        this.string = string;
        this.priority = priority;
    }

    @Override
    public int priority() {
        return priority;
    }

    @Override
    public String toString() {
        return "Entry{" +
                "string='" + string + '\'' +
                ", priority=" + priority +
                '}';
    }
}

        成员变量有 Priority[] arr 自定义大小的数组、size 标记当前元素的个数。

代码如下：

public class OrderedPriorityQueue<E extends Priority> implements Queue<E>{

    private Priority[] arr;
    private int size;

    public OrderedPriorityQueue(int capacity) {
        arr = new Priority[capacity];
    }

}

        4.1 有序数组实现优先级队列 – 入队列 offer(E value)

        使用有序数组实现优先级入队列，在入队列之前从后往前遍历数组，找到优先级小于入队列的元素优先级，找到即可插入其中。

代码如下：

    @Override
    public boolean offer(E value) {
        if (isFull()) {
            return false;
        }
        //先找到优先级比value的优先级大的索引
        int i = size - 1;
        while (i >= 0 && arr[i].priority() > value.priority()) {
            arr[i+1] = arr[i];
            i--;
        }
        arr[i+1] = value;
        size++;
        return true;
    }

        考虑一种情况，若 size == 0 时，为空队列的时候，该代码有无错误？

                答案是：没有问题的，当 size == 0 时， 则 i = 0 – 1，i = -1 ， 此时不会进入循环直接跳到 arr[i + 1] 处，所以，在这种情况下，该代码没有问题。

        4.2 有序数组实现有序队列 – 出队列 poll()

        这就相对于有序数组入队列来说比较简单了，直接在索引为 i = size – 1 处，得到优先级最大的元素，然后将 size– ，再接着 arr[size] 置为 null 。

代码如下：

    @Override
    public E poll() {
        if (isEmpty()) {
            return null;
        }
        E str = (E)arr[size - 1];
        size--;
        arr[size] = null;
        return str;
    }

        注意：需要记录优先级最大的元素并且返回。在出队列之前需要判断该队列是否为空队列。

        4.3 有序数组实现有序队列 – 查看优先级最大的元素 peek()

        先判断该队列是否为空队列，若不是，直接返回该数组索引为 size – 1 处的元素即可。

代码如下：

    @Override
    public E peek() {
        if (isEmpty()) {
            return null;
        }
        E str = (E)arr[size - 1];
        return str;
    }

        4.4 有序数组实现优先级队列 – 判断队列是否为空

        若 size == 0 ，则为空；若不为，则为不空。

代码如下：

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

        4.5 有序数组实现优先级队列 – 判断队列是否为满队列

        若 size == arr.length 时，则为满队列；若不是，则为不满队列。

代码如下：

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

        4.6 有序数组实现优先级队列完整代码

public class OrderedPriorityQueue<E extends Priority> implements Queue<E>{

    private Priority[] arr;
    private int size;

    public OrderedPriorityQueue(int capacity) {
        arr = new Priority[capacity];
    }

    @Override
    public boolean offer(E value) {
        if (isFull()) {
            return false;
        }
        //先找到优先级比value的优先级大的索引
        int i = size - 1;
        while (i >= 0 && arr[i].priority() > value.priority()) {
            arr[i+1] = arr[i];
            i--;
        }
        arr[i+1] = value;
        size++;
        return true;
    }

    @Override
    public E poll() {
        if (isEmpty()) {
            return null;
        }
        E str = (E)arr[size - 1];
        size--;
        arr[size] = null;
        return str;
    }

    @Override
    public E peek() {
        if (isEmpty()) {
            return null;
        }
        E str = (E)arr[size - 1];
        return str;
    }

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

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

        5.0 大顶堆实现优先级队列

        大顶堆说明：

        大顶堆是一种特殊的堆，它是一种完全二叉树，其中每个父节点的值都大于或等于其左右子节点的值。在大顶堆中，根节点的值是整个堆中最大的。

        大顶堆可以使用数组来实现，其中堆的根节点存储在数组的第一个位置，然后按照完全二叉树的性质依次存储其他节点。这种实现方式使得大顶堆的父节点和子节点之间可以通过简单的数学关系来计算，从而方便进行堆调整操作。假设 i 不为 0 ，该双亲索引为：（i – 1）/ 2 ；该左孩子为：2 * i + 1；该右孩子为：2 * i  + 2 。

        首先，需要实现队列中的接口。比如：入队列、出队列等。

接口代码如下：

public interface Queue<E> {

    /**
     * 入队操作
     */
    boolean offer(E value);

    /**
     * 出队操作
     */
    E poll();

    /**
     * 查看队头元素
     */
    E peek();

    /**
     * 判断是否为空队列
     */
    boolean isEmpty();

    /**
     * 判断是否为满队列
     * */
    boolean isFull();
}

         再接着，设置优先级元素。

代码如下：

public class Entry implements  Priority{
    String string;
    int priority;

    public Entry(String string, int priority) {
        this.string = string;
        this.priority = priority;
    }

    @Override
    public int priority() {
        return priority;
    }

    @Override
    public String toString() {
        return "Entry{" +
                "string='" + string + '\'' +
                ", priority=" + priority +
                '}';
    }
}

        成员变量有 Priority[] arr 自定义大小的数组、size 标记当前元素的个数。

代码如下：

public class BigTopPile<E extends Priority> implements Queue<E> {

    private Priority[] arr;
    private int size;

    public BigTopPile(int capacity) {
        arr = new Priority[capacity];
    }

}

        5.1 堆实现优先级队列 – 入队列 offer(E value)

        具体思路为：由于是按照优先级大小来存放元素的，所以，需要先比较优先级大小，在适合的位置插入。现在已知 i = size，该双亲为：（i – 1）/ 2 。接下来，需要判断 arr[（i – 1）/ 2] 的优先级于入队列的元素优先级大小，若 arr[（i – 1）/ 2] 的优先级较大，此时该入队列的元素存放的位置为 arr[i] = value ；若 value 的优先级大于当前 arr[（i – 1）/ 2] 时，先将当前 arr[（i – 1）/ 2] 往后放，即 arr[i] = arr[（i – 1）/ 2] 。之后需要继续往上找双亲，将 i = (i – 1) / 2 ，直到 i == 0 或者 value 的优先级小于当前 arr[（i – 1）/ 2] 时，则为 arr[i] = value 。

代码如下：

    @Override
    public boolean offer(E value) {
        if (isFull()) {
            return false;
        }
        int i = size;
        int j = (i - 1) / 2;
        while (i > 0 && arr[j].priority() < value.priority()) {
            arr[i] = arr[j];
            i = j;
            j = (i - 1) / 2;
        }
        arr[i] = value;
        size++;
        return true;
    }

        只要 i == 0 时， j 不能继续往上走了，否则为抛空指针异常。

        5.2 堆实现优先级队列 – 出队列 poll()

        具体思路为：分为两步。

        第一步，将 arr[size – 1] 处的元素交换到 arr[0] 处。

        第二步，由于根处的优先级永远都要大于该孩子的优先级，所以，将交换之后的元素进行下潜，即先找到该左右孩子优先级最大的元素，于根元素进行交换，一直往下进行下潜。直到该根元素没有左右孩子或者根元素的优先级都大于该左右孩子的优先级。

代码实现：

非递归实现：

    @Override
    public E poll() {
        if (isEmpty()) {
            return null;
        }

        E top = (E)arr[0];
        arr[0] = arr[size - 1];
        size--;
        arr[size] = null;
        int i = 0;
        while ( (i * 2 + 1) < size && (i * 2 + 2) < size && (arr[i].priority() < arr[i * 2 + 1].priority() || arr[i].priority() < arr[i * 2 + 2].priority() ) ) {

            int j = 0;
            if (arr[i * 2 + 1].priority() > arr[i * 2 + 2].priority()) {
                j = i * 2 + 1;
            }else if (arr[i * 2 + 1].priority() <= arr[i * 2 + 2].priority()) {
                j = i * 2 + 2;
            }
            E temp = (E)arr[j];
            arr[j] = arr[i];
            arr[i] = temp;
            i = j;
        }
        return top;
    }

         (i * 2 + 1) < size && (i * 2 + 2) < size 该代码判断的是有无左右孩子元素。

递归实现：

    public E poll1() {
        if (isEmpty()) {
            return null;
        }
        //交换头尾
        swap(0,size - 1);
        size--;
        //置为 null
        E ret = (E)arr[size];
        arr[size] = null;

        //下潜
        down(0);
        return ret;

    }
    private void swap(int i, int j) {
        E t = (E)arr[i];
        arr[i] = arr[j];
        arr[j] = t;
    }
    private void down(int i) {
        int left = 2 * i + 1;
        int right = 2 * i + 2;
        int max = i;
        if ( left < size && arr[max].priority() < arr[left].priority()) {
            max = left;
        }
        if (right < size && arr[max].priority() < arr[right].priority()) {
            max = right;
        }
        if (max != i) {
            swap(max,i);
            down(max);
        }
    }

        

        5.3 堆实现优先级队列 – 查看优先级最大的元素 peek()

        先判断该队列是否为空，若不为空，则直接返回堆顶元素即可。

代码如下：

    @Override
    public E peek() {
        if (isEmpty()) {
            return null;
        }
        return (E)arr[0];
    }

         5.4 堆实现优先级队列 – 判断该队列是否为空

        当 size == 0 时，则为空队列。

代码实现：

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

        5.5 堆实现优先级队列 – 判断该队列是否为满队列

        当 size == arr.length 时，则为满队列。

代码实现：

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

        5.6 堆实现优先级队列完整代码

public class BigTopPile<E extends Priority> implements Queue<E> {

    private Priority[] arr;
    private int size;

    public BigTopPile(int capacity) {
        arr = new Priority[capacity];
    }

    @Override
    public boolean offer(E value) {
        if (isFull()) {
            return false;
        }
        int i = size;
        int j = (i - 1) / 2;
        while (i > 0 && arr[j].priority() < value.priority()) {
            arr[i] = arr[j];
            i = j;
            j = (i - 1) / 2;
        }
        arr[i] = value;
        size++;
        return true;
    }

    @Override
    public E poll() {
        if (isEmpty()) {
            return null;
        }

        E top = (E)arr[0];
        arr[0] = arr[size - 1];
        size--;
        arr[size] = null;
        int i = 0;
        while ( (i * 2 + 1) < size && (i * 2 + 2) < size && (arr[i].priority() < arr[i * 2 + 1].priority() || arr[i].priority() < arr[i * 2 + 2].priority() ) ) {

            int j = 0;
            if (arr[i * 2 + 1].priority() > arr[i * 2 + 2].priority()) {
                j = i * 2 + 1;
            }else if (arr[i * 2 + 1].priority() <= arr[i * 2 + 2].priority()) {
                j = i * 2 + 2;
            }
            E temp = (E)arr[j];
            arr[j] = arr[i];
            arr[i] = temp;
            i = j;
        }
        return top;
    }

    public E poll1() {
        if (isEmpty()) {
            return null;
        }
        //交换头尾
        swap(0,size - 1);
        size--;
        //置为 null
        E ret = (E)arr[size];
        arr[size] = null;

        //下潜
        down(0);
        return ret;

    }
    private void swap(int i, int j) {
        E t = (E)arr[i];
        arr[i] = arr[j];
        arr[j] = t;
    }
    private void down(int i) {
        int left = 2 * i + 1;
        int right = 2 * i + 2;
        int max = i;
        if ( left < size && arr[max].priority() < arr[left].priority()) {
            max = left;
        }
        if (right < size && arr[max].priority() < arr[right].priority()) {
            max = right;
        }
        if (max != i) {
            swap(max,i);
            down(max);
        }
    }



    @Override
    public E peek() {
        if (isEmpty()) {
            return null;
        }
        return (E)arr[0];
    }

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

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

文章出处登录后可见！

已经登录？立即刷新

共计人评分，平均分

到目前为止还没有投票！成为第一位评论此文章。

赞 (0)
xiaoxingxing的头像xiaoxingxing管理团队
0
上一篇 2023年12月15日
下一篇 2023年12月15日

相关推荐