数据结构之优先队列

优先队列PriorityQueue

在数据结构中，普通的队列是先进先出，但有时我们可能并不想有这么固定的规矩，我们希望能有一个带优先级的队列。考虑在现实生活中，一些服务排队窗口会写着“军人依法优先”；送进医院的患者，即便是按顺序到达的，生病更加严重的往往优先级也会更高；还有操作系统中的作业调度也和优先级有关......
于是我们能不能改进队列？使得队列是有一定优先级的，这样能让一些事物和任务的处理变的更加灵活。当然是可以的，最基本的我们可以基于线性结构来实现，考虑基于线性结构的时间复杂度：

结构\操作	入队	出队
普通线性结构	O(1)	O(n)
顺序线性结构	O(n)	O(1)

普通线性结构实现的优先队列出队时间复杂度是O(n)，因为出队要拿出最优先的元素，也就是相对最大的元素（注意：大小是相对的，我们可以指定比较规则），从而要扫描一遍整个数组选出最大的取出才行。而对于顺序线性结构的入队操作，入队后可能破坏了原来的有序性，从而要调整当前顺序。
可以看到使用线性结构总有时间复杂度是O(n)的操作，还有没有更好的实现方式呢，当然是有的，这就要来聊一聊堆Heap。

---

堆

堆严格意义上来说又叫二叉堆（Binary Heap），因为它的结构是一颗完全二叉树，堆一般分为最大堆和最小堆。

最大堆：父亲节点的值大于孩子节点的值
最小堆：父亲节点的值小于孩子节点的值

由于是完全二叉树，节点的索引之间有着一定的关系，故我们可以使用数组来存储二叉堆，具体如下：

Heap

如果从索引为0开始存储，则父亲和孩子节点的索引关系如下：

下面来基于数组实现我们的最大堆，首先是数组类的基本操作：

'''Array.java'''
//本数组具有动态能力，用户不用担心数组空间不够的问题
public class Array<E> {//array盛放的数据类型是E类，这是为了数组的泛型

    private E[] data;
    private int size;//size指向第一个非空位置
    public Array(int capacity){
        //构造函数，传入容量capacity构造Array
        data = (E[])new Object[capacity];
        size = 0;
    }

    public Array(){
        //无参数构造函数
        this(10);//capacity是系统识别的语义
    }
    //服务于最大堆的构造函数
    public Array(E arr[]){
        data = (E[])new Object[arr.length];
        for(int i=0;i<arr.length;i++)
            data[i] = arr[i];
        size = arr.length;
    }
    public int getSize(){
        return size;
    }

    public int getCapacity(){
        return data.length;
    }

    public boolean isEmpty(){
        return size==0;
    }
    public void addLast(E e){
        add(size,e);//与上面等价
    }
    public void addFirst(E e){
        add(0,e);
    }
    public void add(int index, E e){//向索引为index位置插入e
        if(size == data.length)
            resize(2 * data.length);//空间满了则扩容为之前二倍
        if(index < 0 || index > size)
            throw new IllegalArgumentException("add failed,required index > 0 && < size!");
        for(int i = size-1;i>=index;i--)
            data[i+1]=data[i];
        data[index]=e;
        size++;
    }

    E get(int index){//获取index索引位置的元素
        if(index < 0 || index > size)
            throw new IllegalArgumentException("get failed, index is illegal!");
        return data[index];
    }
    void set(int index,E e){//修改index索引位置的元素为e
        if(index < 0 || index > size)
            throw new IllegalArgumentException("set failed, index is illegal!");
        data[index] = e;
    }

    public boolean contains(E e){//查找数组中是否含有e
        for(int i=0;i<size;i++) {
            if (data[i].equals(e))
                return true;
        }
        return false;
    }

    public int find(E e){//查找元素e所在的索引，若不存在元素e，返回-1
        for(int i=0;i<size;i++) {
            if (data[i].equals(e))
                return i;
        }
        return -1;
    }

    public E remove(int index) {//删除索引为index的元素，返回该元素
        if (index < 0 || index > size)
            throw new IllegalArgumentException("Remove failed, index is illegal!");
        E ret = data[index];
        for (int i = index + 1; i < size; i++)
            data[i - 1] = data[i];
        size--;
        data[size] = null;//销毁size位置的空间,本句不是必须
        //loitering object并不等于内存泄漏，不过最好手动释放这种对象的空间

        if(size == data.length/2)//为防止复杂度震荡，可改为除以4
            //if(size == data.length/4&&data.length/2!=0)
            resize(data.length/2);//数组中元素个数减小到一定之前1/2时进行容量缩小
        return ret;
    }

    public E removeFirst(){//删除第一个元素返回其值
        return remove(0);
    }
    public E removeLast(){//删除最后一个元素返回其值
        return remove(size-1);
    }

    public void removeElement(E e){//从数组中删除指定元素e
        int index = find(e);
        if(index!=-1)
            remove(index);
    }
    //服务于最大堆的交换元素函数
    public void swap(int i,int j){
        if(i < 0 || i >= size || j < 0 || j >= size)
            throw new IllegalArgumentException("index is illegal!");
        E t = data[i];
        data[i] = data[j];
        data[j] = t;
    }
    @Override//覆盖父类方法提示，便于微小错误的修改
    public String toString(){
        StringBuilder res = new StringBuilder();
        res.append(String.format("Array:size = %d , capacity = %d\n",size,data.length));
        res.append('[');
        for(int i = 0;i<size;i++){
            res.append(data[i]);
            if(i!=size-1)
                res.append(", ") ;
        }
        res.append(']');
        return res.toString();
    }

    private void resize(int newCapacity){//改变容量函数
        //扩容或缩容只在内部由类自己完成，不能由外部用户操作，对外部透明
        E[] newData= (E[])new Object[newCapacity];
        for(int i=0;i<size;i++)
            newData[i] = data[i];
        data = newData;
    }
}

由于数组类的操作比较简单，没有太多要说明的。接着基于数组的操作构建我们的最大堆类：

public class MaxHeap<E extends Comparable<E>> {
    private Array<E> data;
    public MaxHeap(int capacity){
        data = new Array<>(capacity);
    }
    public MaxHeap(){
        data = new Array<>();
    }

    //将任意数组整理为堆的形状heapify,O(n)
    //实现为构造函数
    public MaxHeap(E arr[]){
        data = new Array<>(arr);
        for(int i=parent(arr.length-1); i >= 0; i --)//最后一个节点的父亲节点即是倒数第一个非叶子节点
            siftDown(i);
    }
    public int size(){
        return data.getSize();
    }
    public boolean isEmpty(){
        return data.isEmpty();
    }
    //辅助函数
    private int parent(int index){
        //返回完全二叉树的数组表示中，一个索引所表示的元素的父亲节点的索引
        if(index == 0)
            throw new IllegalArgumentException("root has no parent!");
        return (index - 1) / 2;
    }
    private int leftChild(int index){
        //返回索引的左孩子的索引
        return index * 2 + 1;
    }
    private int rightChild(int index){
        return index * 2 + 2;
    }

    //添加操作，堆中元素（Sift Up）上浮过程，只需和父亲节点一直比较即可
    public void add(E e){
        data.addLast(e);
        siftUp(data.getSize() - 1);
    }
    private void siftUp(int k){
        //元素上浮过程
        while(k > 0 && data.get(parent(k)).compareTo(data.get(k)) < 0){
            data.swap(k,parent(k));
            k = parent(k);
        }
    }
    //看堆中最大元素
    public E findMax(){
        if(data.getSize()==0)
            throw new IllegalArgumentException("Heap is empty!");
        return data.get(0);
    }
    //取出堆顶元素，把两个堆合成一个堆比较复杂，
    // 于是只需把最后一个元素拿到堆顶，接着元素下沉（Sift Down）过程即可
    public E extractMax(){
        E ret = findMax();
        data.swap(0,data.getSize()-1);
        data.removeLast();
        siftDown(0);
        return ret;
    }
    private void siftDown(int k){
        //和两个孩子比较，如果比自己大，则交换
        while(leftChild(k) < data.getSize()){//若>则是k的左孩子越界，终止循环
            int j = leftChild(k);
            if(j+1 < data.getSize() && data.get(j+1).compareTo(data.get(j)) > 0){//说明当前节点有右孩子
                j = rightChild(k);//如果右孩子大，则j存储右孩子节点索引,j++也可以
                //无论如何此时data[j]中是左右孩子中最大值，j是它们孩子中最大值的索引
            }
            if(data.get(k).compareTo(data.get(j)) >= 0)
                break;//没有违反堆的性质
            data.swap(k,j);
            k = j;
        }
    }
    //取出堆中最大的元素，放入新元素e
    public E replace(E e){
        E ret = findMax();
        data.set(0,e);
        siftDown(0);
        return ret;
    }
}

关于最大堆类需要说明的是replace操作和heapify操作，其中的replace操作实现的功能是取出最大元素（堆顶元素）再放入一个新元素，这个操作的实现可以考虑两种方式：

• 1、先进行extractMax，再执行add操作，这样的时间复杂度是两次O(logn)；
• 2、将新元素代替堆顶元素后执行SiftDown操作，时间复杂度是O(logn)。

我们使用的是第二种，SiftDown是元素下沉过程，它的作用就是调整当前堆结构使其符合最大堆结构。
heapify操作同样可以考虑两种实现：

• 1、将n个元素逐个插入一个空堆，时间复杂度是O(nlogn)；
• 2、将数组看成一棵完全二叉树，从最后一个非叶子节点开始执行SiftDown操作，时间复杂度是O(n)。

我们使用的同样是第二种。

基于堆的优先队列

现在我们就可以用最大堆来完成一个优先队列了，同样，优先队列的基本操作和普通队列的操作是相同的，包括入队出队等，为此我们实现相应的队列接口：

'''Queue.java'''
public interface Queue<E> {
    int getSize();
    boolean isEmpty();
    E dequeue();
    E getFront();
    void enqueue(E e);
}

'''PriorityQueue.java'''
public class PriorityQueue<E extends Comparable<E>> implements Queue<E>{
    private MaxHeap<E> maxHeap;
    public PriorityQueue(){
        //构造函数
        maxHeap = new MaxHeap<>();
    }
    @Override
    public int getSize(){
        return maxHeap.size();
    }
    @Override
    public boolean isEmpty(){
        return maxHeap.isEmpty();
    }
    @Override
    public E getFront(){
        return maxHeap.findMax();
    }
    @Override
    public void enqueue(E e){
        maxHeap.add(e);
    }
    @Override
    public E dequeue(){
        return maxHeap.extractMax();
    }
}

可以看到，在有了堆这种底层数据结构后，优先队列代码非常简洁明了。

优先队列的应用——LeetCode347

来看一道LeetCode上的题目：

LeetCode347

如果单纯用一个数组进行循环，统计各个数字的频率，这样做虽然可行，但时间复杂度会超过O(nlogn)，于是考虑使用优先队列，在这个优先队列中，我们要维护频次最大的k个元素：

• 1、依次入优先队列，不过入队的是元素及其频次的映射，所以要用到TreeMap，直到入队k个不同元素；
• 2、入队k个不同的元素后，每新来一个则和这k个最大元素中频次最小的那个进行比较，如果比较结果是大于则换出这个元素；
• 3、直至数组中所有元素遍历完成，此时优先队列中存储的就是前k个频次最高元素，打印输出即可。

上述伪算法描述中，要每次取出k个元素中最小的元素，所以可以使用最小堆，我们实现的是最大堆，难道还要再实现一个最小堆？其实不用的，所谓的大小是相对的，我们是比较规则的制定者，只需更改比较规则即可，下面给出Solution：

import java.util.LinkedList;
import java.util.List;
import java.util.TreeMap;
//n log k 的复杂度
//使用自己的优先队列
class Solution {
    private class Freq implements Comparable<Freq>{
        public int e, freq;
        public Freq(int e, int freq){
            this.e = e;
            this.freq = freq;
        }
        @Override
        public int compareTo(Freq another){
            //重新定义优先级
            if(this.freq < another.freq)
                return 1;//默认情况compareTo < 时返回 -1；这里我们自己定义了优先级，从而将最大堆相当于转变为最小堆
            else if(this.freq > another.freq)
                return -1;
            else
                return 0;
        }
    }
    public List<Integer> topKFrequent(int[] nums, int k) {
        TreeMap<Integer, Integer> map = new TreeMap<>();
        for(int num:nums){
            if(map.containsKey(num))
                map.put(num,map.get(num)+1);
            else
                map.put(num,1);
        }
        PriorityQueue<Freq> pq = new PriorityQueue<>();
        for(int key: map.keySet()){
            //遍历键
            if(pq.getSize() < k)//没有够k个入优先队列元素,则继续入队
                pq.enqueue(new Freq(key, map.get(key)));
            else {
                if (map.get(key) > pq.getFront().freq) {
                    //够k个新来的则要比较
                    pq.dequeue();//出队
                    pq.enqueue(new Freq(key, map.get(key)));
                }
            }
        }
        LinkedList<Integer> res = new LinkedList<>();
        while(!pq.isEmpty())
            res.add(pq.dequeue().e);
        return res;
    }
}

将它用到的类封装为内部类提交，获得通过！
当然我们也可以使用Java中提供的PriorityQueue，从而简化代码：

import java.util.*;
import java.util.PriorityQueue;
import java.util.Comparator;
public class S5 {
    public List<Integer> topKFrequent(int[] nums, int k) {
        TreeMap<Integer, Integer> map = new TreeMap<>();
        for(int num:nums){
            if(map.containsKey(num))
                map.put(num,map.get(num)+1);
            else
                map.put(num,1);
        }
        PriorityQueue<Integer> pq = new PriorityQueue<>((a,b) -> map.get(a) - map.get(b));
        for(int key: map.keySet()){
            if(pq.size() < k)//没有够k个入优先队列元素,则继续入队
                pq.add(key);
            else {
                if (map.get(key) > map.get(pq.peek())) {
                    //够k个新来的则要比较
                    pq.poll();//出队
                    pq.add(key);
                }
            }
        }
        LinkedList<Integer> res = new LinkedList<>();
        while(!pq.isEmpty())
            res.add(pq.poll());
        return res;
    }
}

Java中的PriorityQueue可传入比较器定义我们的比较原则，此时代码已简化很多，提交，获得通过！

通过