六月丶

优先队列
特征和入队顺序无关,总是最大的元素优先出队。如果说栈是每次输出最先进入的元素,队列是每次输出最后进入的元素,那么优...
扫描右侧二维码阅读全文
18
2020/11

优先队列

特征

和入队顺序无关,总是最大的元素优先出队
如果说栈是每次输出最先进入的元素,队列是每次输出最后进入的元素,那么优先队列就是每次输出优先级最大的元素。

API

优先队列是一种抽象数据类型,他表示了一组值和对这些值的一些操作。我们不一定要用某种固定的存储和操作方式来实现它,只要满足它的特征那它就是优先队列。但怎样才能高效实现它呢?先列出一份API:

public class MAXPQ<T extends Comparable<T>>
MaxPQ()创建一个优先队列
MaxPQ(int max)创建一个初始容量为max的优先队列
MaxPQ(T[] arr)用arr[]中的元素创建一个优先队列
void insert(T a)向队列中插入一个元素
T max()返回最大元素
T delMax()删除并返回最大元素
boolean isEmpty()返回队列是否为空
int size()返回优先队列中的元素个数

实现逻辑

数据结构二叉堆就能很高效的实现这份API。
(堆:当一棵二叉树的某个节点都大于等于它的两个子节点时,它被称为堆有序。)
当有新元素入队时,就把它放入堆的末尾,然后让他自由上浮,直到浮到堆顶或不大于父节点的位置。

入队实现

//添加一个元素
public void insert(T a){
    maxPQ.add(a);
    swim(maxPQ.size()-1);
}
//上浮
private void swim(int idx){
    int fidx = (idx-1)/2;
    if(idx==0||maxPQ.get(fidx).compareTo(maxPQ.get(idx)) >= 0)return;
    Collections.swap(maxPQ,fidx,idx);
    swim(fidx);
}


当要删除最大的元素时,就把堆顶元素(堆顶就是最大元素)和堆末尾元素交换位置,然后删除并返回末尾元素,最后还需要将堆顶元素自由下沉到堆低或不小于子节点的位置。
出队实现

//删除并返回最大元素
public T delmax(){
    if(maxPQ.isEmpty())return null;
    Collections.swap(maxPQ,0,maxPQ.size()-1);
    T max = maxPQ.get(maxPQ.size()-1);
    maxPQ.remove(maxPQ.size()-1);
    if(maxPQ.isEmpty()==false)sink(0);
    return max;
}
//下沉
private void sink(int idx){
    int lastIdx = idx*2+1;
    if(idx<0||idx>=maxPQ.size()||lastIdx>=maxPQ.size())return;
    //如果有右节点且右节点大于左节点
    if(lastIdx<maxPQ.size()-1&&maxPQ.get(lastIdx).compareTo(maxPQ.get(lastIdx+1))<0)lastIdx++;
    if(maxPQ.get(idx).compareTo(maxPQ.get(lastIdx))>=0)return;      //如果大于所有子节点就不下沉了
    Collections.swap(maxPQ,idx,lastIdx);
    sink(lastIdx);
}

完整实现代码

import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.Comparator;

//用堆实现优先队列
public class MaxPQUseArray<T extends Comparable>{
    private ArrayList<T> maxPQ;
    MaxPQUseArray(){maxPQ = new ArrayList<>();}
    //创建一个初始容量为max的优先队列
    MaxPQUseArray(int max){maxPQ = new ArrayList<>();maxPQ.ensureCapacity(max);}
    //用数组初始化优先队列
    MaxPQUseArray(T[] arr){
        maxPQ = new ArrayList<>();
        for(T t:arr){
            insert(t);
        }
    }
    //添加一个元素
    public void insert(T a){
        maxPQ.add(a);
        swim(maxPQ.size()-1);
    }
    //返回最大元素
    public T max(){
        return maxPQ.isEmpty()?null:maxPQ.get(0);
    }
    //删除并返回最大元素
    public T delmax(){
        if(maxPQ.isEmpty())return null;
        Collections.swap(maxPQ,0,maxPQ.size()-1);
        T max = maxPQ.get(maxPQ.size()-1);
        maxPQ.remove(maxPQ.size()-1);
        if(maxPQ.isEmpty()==false)sink(0);
        return max;
    }
    //上浮
    private void swim(int idx){
        int fidx = (idx-1)/2;
        if(idx==0||maxPQ.get(fidx).compareTo(maxPQ.get(idx)) >= 0)return;
        Collections.swap(maxPQ,fidx,idx);
        swim(fidx);
    }
    //下沉
    private void sink(int idx){
        int lastIdx = idx*2+1;
        if(idx<0||idx>=maxPQ.size()||lastIdx>=maxPQ.size())return;
        //如果有右节点且右节点大于左节点
        if(lastIdx<maxPQ.size()-1&&maxPQ.get(lastIdx).compareTo(maxPQ.get(lastIdx+1))<0)lastIdx++;
        if(maxPQ.get(idx).compareTo(maxPQ.get(lastIdx))>=0)return;      //如果大于所有子节点就不下沉了
        Collections.swap(maxPQ,idx,lastIdx);
        sink(lastIdx);
    }
    public boolean isEmpty(){
        return maxPQ.isEmpty();
    }
}

测试用例

当用一个乱序的数组初始化优先队列,然后再依次输出,输出的元素顺序就是有序的了,这也就是著名的堆排序过程。

public static void main(String[] args) {
    Integer[] arr = {2,9,5,1,0,3,6,8,4,7};
    MaxPQUseArray<Integer> maxPQUseArray = new MaxPQUseArray<Integer>(arr);
    while(maxPQUseArray.isEmpty()==false){
        System.out.print(maxPQUseArray.delmax()+" ");
    }
}

输出结果
9 8 7 6 5 4 3 2 1 0

当然在大部分语言的标准库中也有写好的优先队列。

Java

API

Snipaste_2020-11-19_09-50-35.png

测试样例

import java.util.Arrays;
import java.util.PriorityQueue;

public class PriorityQueueDemo {
    public static void main(String[] args) {
        Integer[] arr = {2,5,3,3,8,1,9,6,7,4};
        PriorityQueue<Integer> pque = new PriorityQueue<Integer>(Arrays.asList(arr));
        pque.add(0);
        pque.remove(3);
        System.out.println("size:"+pque.size());
        while(pque.isEmpty()==false){
            System.out.print(pque.poll()+" ");
        }
    }
}

结果

size:10
0 1 2 3 4 5 6 7 8 9

c++

API

Snipaste_2020-11-19_10-13-03.png

测试样例

#include<iostream>
#include<queue>

using namespace std;

int main(){
    int arr[] = {2,6,5,4,1,7,9,8,3};
    priority_queue<int> pque(begin(arr),end(arr));
    pque.push(0);
    cout << "size:" << pque.size() << endl;
    while(!pque.empty()){
        int top = pque.top();
        pque.pop();
        cout << top << " ";
    }
    
    return 0;
}

结果

size:10
9 8 7 6 5 4 3 2 1 0

本文作者:六月丶

本文链接:/index.php/archives/687/

版权声明:如无特别声明,本文即为六月'blog原创,仅代表个人观点,如要转载请务必注明文章出处。
最后修改:2020 年 11 月 19 日 10 : 31 AM
如果觉得我的文章对你有用,请随意赞赏

发表评论