优先级队列

1. 优先级队列

---

1. 1 前言

队列是一种基于先进先出(FIFO)的数据结构，但是在某些情况下，我们操作的数据可能带有优先级，这时候通常要求我们将优先级高的元素先出队列，在这种情况下使用普通的队列就不能满足我们的需求，因此我们就需要能够根据优先级返回优先级对象的数据结构，这就是优先级队列(PriorityQueue)

1.2 堆(Heap)

PriorityQueue底层使用了堆这种数据结构，那么什么是堆呢？如果有一个关键码的集合K = {k0，k1， k2，…，kn-1}，把它的所有元素按完全二叉树的顺序存储方式存储在一个一维数组中，并满足：Ki <= K(2i+1) 且 Ki<= K(2i+2) (或满足：Ki >= K(2i+1) 且 Ki >= K(2i+2)) ;i = 0，1，2…，则称为 小根堆(或大根堆)。将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。简单来说，堆就是一个完全二叉树按层序遍历的顺序存储方式存储在一个数组中

1.3 堆的创建

在堆的创建过程中，我们会使用到向下调整算法，那么什么是向下调整算法呢？这里以建立小根堆为例，首先我们要明确使用向下调整算法的前提：当左、右子树都是小根堆时可以使用向下调整算法将这颗树调整成小根堆。

那么向下调整的过程是怎样的呢？我们将当前需要调整的结点记为root结点，child标记它左右孩子中的最小值，然后将root结点标记的结点与child结点标记的内容进行比较，当root结点的值比child结点的值小时，此时代表该堆已经是小根堆，调整结束；当root结点的值比child结点的值大时，交换root结点和child结点的值，然后让root结点标记当前child结点，child结点接着标记root结点的孩子结点的最小值，直到比较到底或满足小根堆条件结束。

#向下调整

//向下调整：  前提：左右子树都是小根堆
private void shiftDown(int root, int len) {  
    int child = root * 2 + 1;  
    //当child < len 时，此时说明待调整结点已经是小根堆
    while(child < len) {  
        //找孩子节点中大的  
        if (child + 1 < len && this.elem[child] > this.elem[child + 1]) {  
            child++;  
        }  
        if (elem[child] < elem[root]) {  
            //交换后可能打乱下面小根堆，接着向下调整  
            swap(elem, child, root);  
            root = child;  
            child = 2 * root + 1;  
        }else {  
            return ;  
        }  
    }  
}

向下调整算法要求我们待调整结点的左右子树都是小根堆，那么对于一个普通的数组序列，它的根节点的左右子树不满足使用向下调整算法的前提，对于这种情况，我们又该如何调整呢？(对于一个普通序列，如何建立一个小根堆呢？)

对于叶子节点而言，它不存在左右子树，也就是说它天然满足向下调整的条件；同样对于左右子树都是只有一个结点的树，左右子树也是天然满足都是小根堆的条件的，又因为堆中的所有元素都是按完全二叉树的顺序存储方式存储在一个一维数组中，所以当我们找到倒数第一个非叶子节点，从该节点位置开始往前调整一直到根节点，遇到的每一个结点都向下调整，就能建立一个小根堆。

//使用向下调整算法结束时，该堆就是小根堆
public void creatHeap(int[] arr) {  
    this.elem = Arrays.copyOf(arr,arr.length);  
    this.usedSize = arr.length;  
    for(int i = (usedSize - 1 - 1) / 2;i >= 0;i--) {  
        //从倒数第一个非叶子节点开始调整;即从最下面开始调整  
        shiftDown(i,usedSize);  //usedSize作为结束条件
    }  
}

需要注意的是在使用向下调整算法时，我们应该传递一个长度作为结束条件。

时间复杂度能够衡量一个算法的好坏，那么在建堆过程中的时间复杂度是多少呢？
建堆过程移动结点的总步数大概为T(N) = N - Log2(N + 1),也就是说建堆的时间复杂度为O(N)

1.4 堆的插入与删除

对于一个已经确认元素数量的普通序列，我们可以通过从倒数第一个非叶子节点开始往前使用向下调整的方式来建立小根堆，从而将普通序列转换成一个小根堆，那么对于一个不确定元素个数，即可能根据使用情况而有所增加的序列，我们该如何解决呢？

1.4.1 堆的插入

堆的插入其实只需要两个步骤：

1. 将元素放入到数组的底层空间(原最后一个有效元素后面)，当空间不足时需要扩容
2. 对新插入的结点进行向上调整，直到满足堆的属性。
   

对于向上调整算法，我们只需要将新插入的元素和它的父节点进行比较就可以，根据比较结果来确定是否继续向上调整，因为原来的结构已经满足小根堆结构，所以只需与父节点比较即可。

//根据调整结果决定是否接着向上调整
private void shilfUp(int root) {  
    int parent = (root - 1) / 2;  
    while(parent >= 0) {  
        if(elem[root] < elem[parent]) {  
            //交换后可能影响小根堆顺序，接着向上调整  
            swap(elem,root,parent);  
            root = parent;  
            parent = (root - 1) / 2;  
        }else {  
            return ;  
        }  
    }  
}

1.4.2 堆的删除

前面我们提到优先级队列是利用堆这种数据结构来实现的，也就是说堆的删除应该能依据优先级来删除，所以堆的删除一定是删除堆顶元素，那么该如何实现堆的删除呢？

1. 交换堆顶元素和堆中的最后一个元素。
2. 将堆中有效数据个数减少一个，因为我们要将交换后的堆中的最后一个元(原堆顶元素)素剔除。
3. 对现堆顶元素进行向下调整(交换元素时，打乱了当前堆顶元素的小根堆结构)

//实现出队操作:队头和队尾交换
public int poll() {  
    if(isEmpty()) {  
        throw new EmptyException("优先级队列为空，poll失败");  
    }  
    swap(elem,0,--this.usedSize);  
    //再对对头进行一次向下调整  
    shiftDown(0,this.usedSize);  
    return this.elem[this.usedSize];  
}

1.5 堆模拟实现优先级队列

import java.util.Arrays;  
  
public class PriorityQueue {  
    public int[] elem;  
    public int usedSize;  
  
    public PriorityQueue() {  
        this.elem = new int[10];  
    }  
    public void initElem(int[] arr) {  
        for (int i = 0; i < arr.length; i++) {  
            this.elem[i] = arr[i];  
            this.usedSize++;  
        }  
    }  
  
    //建堆:以建小根堆为例  
    public void creatHeap(int[] arr) {  
        this.elem = Arrays.copyOf(arr,arr.length);  
        this.usedSize = arr.length;  
        for(int i = (usedSize - 1 - 1) / 2;i >= 0;i--) {  
            //从倒数第一个非叶子节点开始调整;即从最下面开始调整  
            shiftDown(i,usedSize);  
        }  
    }  
    //向下调整要求：左子树和右子树都是大根堆  
    private void shiftDown(int root, int len) {  
        int child = root * 2 + 1;  
        while(child < len) {  
            //找孩子节点中大的  
            if (child + 1 < len && this.elem[child] > this.elem[child + 1]) {  
                child++;  
            }  
            if (elem[child] < elem[root]) {  
                //交换后可能打乱下面小根堆，接着向下调整  
                swap(elem, child, root);  
                root = child;  
                child = 2 * root + 1;  
            }else {  
                return ;  
            }  
        }  
    }  
  
    private void swap(int[] elem, int i, int j) {  
        int tmp = elem[i];  
        elem[i] = elem[j];  
        elem[j] = tmp;  
    }  
  
    //实现入队操作  
    public void offer(int val) {  
        //判断队列是否满  
        if(isFull()) {  
            getExpansion();  
        }  
        this.elem[this.usedSize] = val;  
        //借助向上调整算法O（N*LogN）,调整优先级队列顺序  
        shilfUp(this.usedSize++);  
    }  
  
    private void shilfUp(int root) {  
        int parent = (root - 1) / 2;  
        while(parent >= 0) {  
            if(elem[root] < elem[parent]) {  
                //交换后可能影响小根堆顺序，接着向上调整  
                swap(elem,root,parent);  
                root = parent;  
                parent = (root - 1) / 2;  
            }else {  
                return ;  
            }  
        }  
    }  
  
    private boolean isFull() {  
        return this.elem.length == usedSize;  
    }  
    private void getExpansion() {  
        this.elem = Arrays.copyOf(elem,elem.length * 2);  
    }  
    public boolean isEmpty() {  
        return this.usedSize == 0;  
    }  
  
    //实现出队操作:队头和队尾交换  
    public int poll() {  
        if(isEmpty()) {  
            throw new EmptyException("优先级队列为空，poll失败");  
        }  
        swap(elem,0,--this.usedSize);  
        //再对对头进行一次向下调整  
        shiftDown(0,this.usedSize);  
        return this.elem[this.usedSize];  
    }  
    //peek  
    public int peek() {  
        if(isEmpty()) {  
            throw new EmptyException("优先级队列为空，peek失败");  
        }  
        return this.elem[0];  
    }  
    public int size() {  
        return this.usedSize;  
    }  
    public void clear() {  
        for (int i = 0; i < this.usedSize; i++) {  
            elem[i] = 0;  
        }  
        elem = null;  
    }  
}

在使用编译器提供的PriorityQueue时要注意：

1. PriorityQueue中放置的元素必须要能够比较大小，不能插入无法比较大小的对象，否则会抛出ClassCastException异常
2. 不能插入null对象，否则会抛出NullPointerException
3. PriorityQueue底层使用了堆数据结构，默认情况下建立的是小根堆
4. 插入和删除元素的时间复杂度为O（LogN）
5. Top-K问题的解决常用优先级队列

#Top-K： 求数据集合中前K个最大的元素或者最小的元素

1. 用数据集合中前K个元素来建堆(前k个最大的元素，则建小堆；前k个最小的元素，则建大堆)
2. 用剩余的N-K个元素依次与堆顶元素来比较，不满足则替换堆顶元素

PriorityQueue常使用构造方法

构造方法	功能介绍
PriorityQueue()	创建一个空的优先级队列，默认容量是11
PriorityQueue(int initialCapacity)	创建一个初始容量为initialCapacity的优先级队列，注意：initialCapacity不能小于1，否则会抛IllegalArgumentException异常
PriorityQueue(Collection<? extends E> c)	用一个集合来创建优先级队列

原文地址：https://blog.csdn.net/2302_79249715/article/details/142766134

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！