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

简介: 本文介绍了优先级队列的概念及其底层数据结构——堆。优先级队列根据元素的优先级而非插入顺序进行出队操作。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);
    }
}

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

目录
打赏
0
5
5
0
95
分享
相关文章
java实现队列数据结构代码详解
本文详细解析了Java中队列数据结构的实现,包括队列的基本概念、应用场景及代码实现。队列是一种遵循“先进先出”原则的线性结构,支持在队尾插入和队头删除操作。文章介绍了顺序队列与链式队列,并重点分析了循环队列的实现方式以解决溢出问题。通过具体代码示例(如`enqueue`入队和`dequeue`出队),展示了队列的操作逻辑,帮助读者深入理解其工作机制。
110 1
232.用栈实现队列,225. 用队列实现栈
在232题中,通过两个栈(`stIn`和`stOut`)模拟队列的先入先出(FIFO)行为。`push`操作将元素压入`stIn`,`pop`和`peek`操作则通过将`stIn`的元素转移到`stOut`来实现队列的顺序访问。 225题则是利用单个队列(`que`)模拟栈的后入先出(LIFO)特性。通过多次调整队列头部元素的位置,确保弹出顺序符合栈的要求。`top`操作直接返回队列尾部元素,`empty`判断队列是否为空。 两题均仅使用基础数据结构操作,展示了栈与队列之间的转换逻辑。
|
6月前
|
【C++数据结构——栈与队列】顺序栈的基本运算(头歌实践教学平台习题)【合集】
本关任务:编写一个程序实现顺序栈的基本运算。开始你的任务吧,祝你成功!​ 相关知识 初始化栈 销毁栈 判断栈是否为空 进栈 出栈 取栈顶元素 1.初始化栈 概念:初始化栈是为栈的使用做准备,包括分配内存空间(如果是动态分配)和设置栈的初始状态。栈有顺序栈和链式栈两种常见形式。对于顺序栈,通常需要定义一个数组来存储栈元素,并设置一个变量来记录栈顶位置;对于链式栈,需要定义节点结构,包含数据域和指针域,同时初始化栈顶指针。 示例(顺序栈): 以下是一个简单的顺序栈初始化示例,假设用C语言实现,栈中存储
301 77
|
5月前
|
STL——栈和队列和优先队列
通过以上对栈、队列和优先队列的详细解释和示例,希望能帮助读者更好地理解和应用这些重要的数据结构。
81 11
☀☀☀☀☀☀☀有关栈和队列应用的oj题讲解☼☼☼☼☼☼☼
### 简介 本文介绍了三种数据结构的实现方法:用两个队列实现栈、用两个栈实现队列以及设计循环队列。具体思路如下: 1. **用两个队列实现栈**: - 插入元素时,选择非空队列进行插入。 - 移除栈顶元素时,将非空队列中的元素依次转移到另一个队列,直到只剩下一个元素,然后弹出该元素。 - 判空条件为两个队列均为空。 2. **用两个栈实现队列**: - 插入元素时,选择非空栈进行插入。 - 移除队首元素时,将非空栈中的元素依次转移到另一个栈,再将这些元素重新放回原栈以保持顺序。 - 判空条件为两个栈均为空。
|
6月前
|
C++
【C++数据结构——栈和队列】括号配对(头歌实践教学平台习题)【合集】
【数据结构——栈和队列】括号配对(头歌实践教学平台习题)【合集】(1)遇到左括号:进栈Push()(2)遇到右括号:若栈顶元素为左括号,则出栈Pop();否则返回false。(3)当遍历表达式结束,且栈为空时,则返回true,否则返回false。本关任务:编写一个程序利用栈判断左、右圆括号是否配对。为了完成本关任务,你需要掌握:栈对括号的处理。(1)遇到左括号:进栈Push()开始你的任务吧,祝你成功!测试输入:(()))
164 7
|
8月前
|
【数据结构】栈和队列(c语言实现)(附源码)
本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表,遵循“先进后出”原则;队列则在一端插入、另一端删除,遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现,并提供了完整的代码示例。栈和队列在实际应用中非常广泛,如二叉树的层序遍历和快速排序的非递归实现等。
754 9
|
8月前
|
非递归实现后序遍历时,如何避免栈溢出?
后序遍历的递归实现和非递归实现各有优缺点,在实际应用中需要根据具体的问题需求、二叉树的特点以及性能和空间的限制等因素来选择合适的实现方式。
186 59
栈区的非法访问导致的死循环(x64)
这段内容主要分析了一段C语言代码在VS2022中形成死循环的原因,涉及栈区内存布局和数组越界问题。代码中`arr[15]`越界访问,修改了变量`i`的值,导致`for`循环条件始终为真,形成死循环。原因是VS2022栈区从低地址到高地址分配内存,`arr`数组与`i`相邻,`arr[15]`恰好覆盖`i`的地址。而在VS2019中,栈区先分配高地址再分配低地址,因此相同代码表现不同。这说明编译器对栈区内存分配顺序的实现差异会导致程序行为不一致,需避免数组越界以确保代码健壮性。
23 0
栈区的非法访问导致的死循环(x64)
|
6月前
|
【C++数据结构——栈与队列】环形队列的基本运算(头歌实践教学平台习题)【合集】
【数据结构——栈与队列】环形队列的基本运算(头歌实践教学平台习题)【合集】初始化队列、销毁队列、判断队列是否为空、进队列、出队列等。本关任务:编写一个程序实现环形队列的基本运算。(6)出队列序列:yzopq2*(5)依次进队列元素:opq2*(6)出队列序列:bcdef。(2)依次进队列元素:abc。(5)依次进队列元素:def。(2)依次进队列元素:xyz。开始你的任务吧,祝你成功!(4)出队一个元素a。(4)出队一个元素x。
222 13
【C++数据结构——栈与队列】环形队列的基本运算(头歌实践教学平台习题)【合集】
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等