【数据结构】优先级队列(堆)从实现到应用详解

简介: 本文介绍了优先级队列的概念及其底层数据结构——堆。优先级队列根据元素的优先级而非插入顺序进行出队操作。JDK1.8中的`PriorityQueue`使用堆实现,堆分为大根堆和小根堆。大根堆中每个节点的值都不小于其子节点的值,小根堆则相反。文章详细讲解了如何通过数组模拟实现堆,并提供了创建、插入、删除以及获取堆顶元素的具体步骤。此外,还介绍了堆排序及解决Top K问题的应用,并展示了Java中`PriorityQueue`的基本用法和注意事项。

🍁1. 优先级队列的概念

在之前已经了解过,队列是一种先进先出的数据结构,而优先级队列是一种抽象数据类型,其中每个元素都有一个优先级。与标准的队列不同,优先级队列中元素的顺序是根据其优先级来决定的,而不是按插入的顺序,优先级高的元素将优先出队。

JDK1.8中的PriorityQueue底层使用了堆这种数据结构,而堆实际就是在完全二叉树的基础上进行了一些调整。

🍁2. 堆的介绍

堆是一种特殊的完全二叉树结构,堆又可以分为大根堆和小根堆

大根堆:每个节点的值都大于或等于其子节点的值,也就是根节点是树中的最大值。

小根堆:每个节点的值都小于或等于其子节点的值,也就是根节点包含树中的最小值。

🍁3. 堆的模拟实现

底层通过数组来实现堆

public class MyHeap {
    public int[] elem;
    public int usedSize;
    public MyHeap(int[] elem) {
        this.elem = elem;
    }
}

将元素存储在数组中后,如果孩子节点的下标为i,那么双亲节点的下标为(i - 1)/ 2

如果双亲节点的下标为 i ,那么左孩子的下标为 2*i+1,右孩子的下标为 2*i+2,如果左孩子或右孩子下标越界了就表示没有左孩子或右孩子

明白了节点怎么表示后就可以根据这些关系进行建堆了,

从最后一棵子树开始,依次往上调用向下调整

public void createHeap() {
    //最后一棵子树
    for (int parent = (usedSize - 1 - 1) / 2; parent >= 0; parent--) {
        siftDown(parent, this.usedSize);
    }
}

🍁3.1 向下调整建堆

向上调整通常指的是在插入新元素到堆中后,为了确保堆的性质(父节点的值总是大于或等于(最大堆)或小于或等于(最小堆)其子节点的值),对堆进行调整

以大根堆的创建为例:

通过双亲节点计算出左孩子节点的下标,如果左孩子存在,就继续判断右孩子是否存在,如果右孩子也存在并且右孩子大于左孩子,就把child的位置更新为右孩子,接着和双亲节点进行比较,如果比双亲节点大,就交换,以此循环调整

private void siftDown(int parent, int usedSize) {
    int child = parent * 2 + 1;
    while (child < usedSize) {
        //右孩子大于左孩子的情况,更新孩子节点
        if (child + 1 < usedSize && elem[child] < elem[child + 1]) {
            child++;
        }
        if (elem[child] > elem[parent]) {
            int tmp = elem[parent];
            elem[parent] = elem[child];
            elem[child] = tmp;
            //往下更新双亲节点和孩子节点
            parent = child;
            child = child * 2 + 1;
        } else {
            break;
        }
    }
}

这个时间复杂度通过推导得出是一个O(n)的

🍁3.2 向上调整

给出一个孩子节点,再求出双亲节点,接着比较双亲节点和孩子节点,进行调整,这里的结束条件是双亲节点小于或等于0,意味着此时已经调整到了堆顶

还是以大根堆为例,由于大根堆要求的是双亲节点要大于孩子节点,所以无论是左孩子还是右孩子比双亲节点大,都需要交换,所以这里就不用区分左孩子还是右孩子了,都按照左孩子节点进行

private void siftUp(int child){
int parent = (child - 1) / 2;
while(parent >= 0){
    if(elem[child] > elem[parent]){
        int tmp = elem[child];
        elem[child] = elem[parent];
        elem[parent] = tmp;
        child = parent;
        parent = (child - 1) / 2;
    }else{
        break;
    }
}
}

向上调整的方法由于比向下调整多了最后一层的操作,所以时间复杂度为O(n + logn)

🍁3.3  插入

插入的思路就是先把元素放在最后,接着调用向上调整,依次把要插入的元素调整到适合的位置

public void offer(int val){
if(isFull()){
    elem = Arrays.copyOf(elem,2*elem.length);
}
elem[usedSize] = val;
//调用向上调整
siftUp(usedSize);
usedSize++;
}
public boolean isFull(){
    return usedSize == elem.length;
}

🍁3.4 删除

思路:把根节点和最后一个节点交换,接着把usedSize--,这样就达到了删除的效果,并且此时只有根节点不满足大根堆的条件,只需要再次调用向下调整,就符合了大根堆

public int poll(){
    if(isEmpty()){
        throw new QueueEmptyException("队列为空");
    }
    int val = elem[0];
    //把根节点元素交换到末尾
    swap(elem,0,usedSize-1);
    siftDown(0,usedSize-1);
    //usedSize--就表示已经删除了
    usedSize--;
    return val;
}

🍁3.5 获取堆顶元素

直接对堆顶元素进行返回即可

public int peek(){
    if(isEmpty()){
        throw new QueueEmptyException("队列为空");
    }
    return elem[0];
}

🍁4. 堆的应用

🍁4.1 堆排序

将一组数据从小到大进行排序,使用到的是大根堆,大根堆的根节点肯定是最大的,然后把根节点和末尾元素交换,接着进行向下调整,然后新的根节点再和倒数第二个元素交换,以此类推,最终就可以实现从小到大排序的效果

public void heapSort(){
    int end = usedSize - 1;
    while(end > 0){
        swap(elem,0,end);//交换
        siftDown(0,end);//调整
        end--;//更新
    }
}

堆排序的时间复杂度是nlogn,如果加上创建堆,就是n + nlogn,依旧是nlogn

🍁4.2 top k 问题

topk 问题指的是求出数据集合中前k个最大或最小的元素

例如求出前k个最小的元素,会有以下几种方法:

1.整体进行排序,取出前k个元素

2.创建小根堆,拿出k个堆顶元素

3.把前k个元素创建为大根堆,遍历剩下的N-k个元素,和堆顶元素比较,如果比堆顶元素小,就删除堆顶元素,当前元素入堆,遍历完成后小根堆中的k个元素即为所求

第三种方法,当k很小时时间复杂度就趋近于o(n),是比前面的两种高效的

来看一道力扣上的面试题:

面试题 17.14. 最小K个数

class IntCmp implements Comparator<Integer>{
    @Override
    public int compare(Integer o1, Integer o2) {
        return o2.compareTo(o1);
    }
}
class Solution {
    public int[] smallestK(int[] arr, int k) {
        int[] res = new int[k];
        if(arr == null || k == 0){
            return res;
        }
        PriorityQueue<Integer> queue = new PriorityQueue<>(k, new IntCmp());
        for (int i = 0; i < k; i++) {
            queue.offer(arr[i]);
        }
        for (int i = k; i < arr.length; i++) {
            if (arr[i] < queue.peek()) {
                queue.poll();
                queue.offer(arr[i]);
            }
        }
        for (int i = k - 1; i >= 0; i--) {
            res[i] = queue.poll();
        }
        return res;
    }
}

🍁5. Java中PriorityQueue的使用

使用PriorityQueue时需要注意:

1. 放置的元素必须能够比较大小,不能插入无法比较大小的对象,否则会抛出异常

2. 不能插入null对象,否则会空指针异常

3. 插入和删除的时间复杂度为O(log ₂ n)

4. 默认情况下是小根堆

我们来演示一下这些构造方法

public class PriorityQueueDemo {
    public static void main(String[] args) {
        //创建一个默认容量的优先级队列
        PriorityQueue<Integer> queue1 = new PriorityQueue<>();
        //创建一个100容量的优先级队列
        PriorityQueue<Integer> queue2 = new PriorityQueue<>(100);
        //传入ArrayList对象创建对象
        ArrayList<Integer> arrayList = new ArrayList<>();
        arrayList.add(3);
        arrayList.add(1);
        arrayList.add(2);
        PriorityQueue<Integer> queue3 = new PriorityQueue<>(arrayList);
        System.out.println(queue3);
    }
}

很明显,最终的结果也是一个小根堆的形式,如果想要创建大根堆需要传入相应的比较器

class IntCmp implements Comparator<Integer>{
    @Override
    public int compare(Integer o1, Integer o2) {
        return o2.compareTo(o1);//Integer类型不能用 "-" 比较
    }
}
public class PriorityQueueDemo {
    public static void main(String[] args) {
        //传入比较器对象     
        PriorityQueue<Integer> queue4 = new PriorityQueue<>(new IntCmp());
        queue4.add(3);
        queue4.add(1);
        queue4.add(2);
        System.out.println(queue4);
    }
}

此外,其他的方法和上面实现的一样

相关文章
|
4天前
|
缓存 算法 调度
数据结构之 - 双端队列数据结构详解: 从基础到实现
数据结构之 - 双端队列数据结构详解: 从基础到实现
20 5
|
4天前
|
存储 算法 搜索推荐
探索常见数据结构:数组、链表、栈、队列、树和图
探索常见数据结构:数组、链表、栈、队列、树和图
78 64
|
4天前
|
消息中间件 存储 Java
数据结构之 - 深入探析队列数据结构: 助你理解其原理与应用
数据结构之 - 深入探析队列数据结构: 助你理解其原理与应用
12 4
|
4天前
|
存储 算法 分布式数据库
【初阶数据结构】理解堆的特性与应用:深入探索完全二叉树的独特魅力
【初阶数据结构】理解堆的特性与应用:深入探索完全二叉树的独特魅力
|
4天前
【初阶数据结构】深入解析队列:探索底层逻辑
【初阶数据结构】深入解析队列:探索底层逻辑
|
2天前
【数据结构】大根堆和小根堆
【数据结构】大根堆和小根堆
10 0
|
3天前
|
存储 算法 搜索推荐
数据结构--堆的深度解析
数据结构--堆的深度解析
|
3天前
|
存储 算法 调度
数据结构--二叉树的顺序实现(堆实现)
数据结构--二叉树的顺序实现(堆实现)
|
13天前
|
算法 安全 测试技术
golang 栈数据结构的实现和应用
本文详细介绍了“栈”这一数据结构的特点,并用Golang实现栈。栈是一种FILO(First In Last Out,即先进后出或后进先出)的数据结构。文章展示了如何用slice和链表来实现栈,并通过golang benchmark测试了二者的性能差异。此外,还提供了几个使用栈结构解决的实际算法问题示例,如有效的括号匹配等。
golang 栈数据结构的实现和应用
|
4天前
|
Go
数据结构之 - 深入了解栈数据结构
数据结构之 - 深入了解栈数据结构
13 5