乐趣区

关于java:面试官再问你优先级队列请把这篇文章丢给他

jiezi

程序员罕用的 IDEA 插件：https://github.com/silently9527/ToolsetIdeaPlugin

齐全开源的淘客我的项目：https://github.com/silently9527/mall-coupons-server

微信公众号：贝塔学 Java

前言

如果你设计的事件零碎中有很多的事件，每个事件都定义了不同的权重值，零碎须要优先解决权重较高的事件，这里你就须要应用到优先级队列，本篇咱们一起来学习实现优先级队列的罕用形式

队列 API 定义

在实现之前，首先咱们须要先定义出优先级队的 API，优先级队列是一种形象的数据结构，咱们仍然能够基于后面咱们应用到的队列 API 来批改；须要理解之前的队列的实现能够查看《面试的节令到了，老哥确定不来温习下数据结构吗》

public interface Queue<T> extends Iterable<T> {void enqueue(T item); // 入队列

    T dequeue(); // 出队列

    int size();

    boolean isEmpty();}

其中的入队列 enqueue 和出队列 dequeue 是咱们次要须要实现的形式，也是优先级队列的外围办法

高级版本的实现

队列 API 的抽象类

public abstract class AbstractQueue<T> implements Queue<T> {
    private Comparator<T> comparator;

    public AbstractQueue(Comparator<T> comparator) {this.comparator = comparator;}

    public boolean less(T a, T b) {return comparator.compare(a, b) < 0;
    }

    public void exch(T[] array, int i, int j) {T tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }
}

基于无序数组实现

实现优先级队列的最简略实现能够参考《面试的节令到了，老哥确定不来温习下数据结构吗》中栈的实现形式，enqueue和栈的 push 形式实现形式统一，dequeue能够参考抉择排序的实现，循环一遍数组，找出最大值和数组最初一个元素替换，而后删除它；

public class DisorderPriorityQueue<T> extends AbstractQueue<T> {private T[] queue;
    private int size;

    public DisorderPriorityQueue(int max, Comparator<T> comparator) {super(comparator);
        this.queue = (T[]) new Object[max];
    }

    @Override
    public void enqueue(T item) {queue[size++] = item;
    }

    @Override
    public T dequeue() {
        int index = 0;
        for (int i = 1; i < size; i++) {if (less(queue[index], queue[i])) {index = i;}
        }
        size--;
        exch(queue, index, size);
        T data = queue[size];
        queue[size] = null;
        return data;
    }
    // 省略其余函数
}

这里只实现了定长的优先级队列，如何实现主动扩容呢？也能够参考这篇文章《面试的节令到了，老哥确定不来温习下数据结构吗》；基于无序数组实现的 enqueue 工夫复杂度是 O(1)，dequeue 工夫复杂度是 O(n)

基于有序数组实现

基于有序数组实现就是在入队的时候保障数组有序，那么在出队列的时候能够间接删掉最大值；插入的过程和插入排序相似的操作

public class OrderPriorityQueue<T> extends AbstractQueue<T> {private T[] queue;
    private int size;

    public OrderPriorityQueue(int max, Comparator<T> comparator) {super(comparator);
        this.queue = (T[]) new Object[max];
    }

    @Override
    public void enqueue(T item) {queue[size++] = item;
        for (int i = size - 1; i > 1 && less(queue[i], queue[i - 1]); i--) {exch(queue, i, i - 1);
        }
    }

    @Override
    public T dequeue() {
        size--;
        T data = queue[size];
        queue[size] = null;
        return data;
    }

    // 省略其余函数
}

enqueue 工夫复杂度是 O(n)，dequeue 工夫复杂度是 O(1)

基于链表实现

基于链表的实现与下面的相似，有趣味的能够本人实现

在《面试的节令到了，老哥确定不来温习下数据结构吗》中咱们实现的栈和队列的操作都可能在常数工夫内实现，然而优先级队列从下面的实现过程，咱们发现高级版本的实现插入或删除最大值的操作最蹩脚的状况会是线性工夫。

二叉堆实现

二叉堆的定义

在二叉堆中，每个节点都将大于等于它的子节点，也成为堆有序；其中根节点是最大的节点。

二叉堆的示意：

重点：
在一个二叉堆中，地位 k 节点的父节点的地位为 k/2, 它的两个子节点的地位为2k 和2k+1; 基于这点，咱们能够用数组来示意二叉堆，通过挪动数组的下标来找到节点父节点和子节点

在元素进行插入和删除操作的过程中，会毁坏堆有序，所以咱们须要做一些操作来保障堆再次有序；次要有两种状况，当某个节点的优先级回升，咱们须要 由下向上复原堆有序（下沉）；当某个节点优先级降落，咱们须要 由上向下复原堆有序（上浮）

由上向下复原堆有序（上浮）

private void swim(int k) {while (k > 0 && less(queue[k / 2], queue[k])) {exch(queue, k / 2, k);
        k = k / 2;
    }
}

依据以后的节点 k 找到父节点的地位 k /2，比拟以后节点和父节点，如果比父节点大就替换，直到找个比以后节点大的父节点或者已上浮到了根节点

由下向上复原堆有序（下沉）

private void sink(int k) {while (2 * k <= size) {
        int i = 2 * k;
        if (less(queue[i], queue[i + 1])) {i++;}
        if (less(queue[i], queue[k])) {break;}
        exch(queue, i, k);
        k = i;
    }
}

二叉堆实现优先级队列

  • 入队操作：将新的元素增加到数组开端，让新元素上浮到适宜地位，减少堆的大小
  • 出队操作：将最大的根节点删除，而后把最初一个元素放入到顶端，上层顶端元素到适合地位，减小堆大小
public class BinaryHeapPriorityQueue<T> extends AbstractQueue<T> {private T[] queue;
    private int size;

    public BinaryHeapPriorityQueue(int max, Comparator<T> comparator) {super(comparator);
        this.queue = (T[]) new Object[max + 1];
    }

    @Override
    public void enqueue(T item) {this.queue[++size] = item;
        this.swim(size);
    }

    @Override
    public T dequeue() {T max = this.queue[1];
        exch(this.queue, 1, size--);
        this.queue[size + 1] = null; // 开释内存
        this.sink(1);
        return max;
    }
    
     // 省略其余函数
}

留神：

因为咱们为了不便计算父节点和子节点的索引地位，所以数组中的第一个地位是不会应用的；能够本人思考下应用第一个地位，那么子节点和父节点的地位应该如何计算？

基于堆的实现，入队和出队的工夫简单对都是 logN，解决了高级版本实现的问题。

数组大小动静扩容和缩容仍然能够参考之前栈的实现形式

文中所有源码已放入到了 github 仓库 https://github.com/silently9527/JavaCore

最初（点关注，不迷路）

文中或者会存在或多或少的有余、谬误之处，有倡议或者意见也十分欢送大家在评论交换。

最初，写作不易，请不要白嫖我哟 ，心愿敌人们能够 点赞评论关注 三连，因为这些就是我分享的全副能源起源????

退出移动版