优先级队列(堆)

目录

一、优先级队列

1、概念

2、优先级队列的模拟实现

2.1 堆的概念

2.2 堆的存储方式

2.3 堆的创建

 2.3.1 堆向下调整

2.3.2 堆的创建

2.4 堆的插入与删除

2.4.1 堆的插入

2.4.2 堆的删除  

2.5 用堆模拟实现优先级队列 

3.常用接口介绍

3.1 PriorityQueue的特性

3.2 PriorityQueue常用接口介绍

1. 优先级队列的构造

2. 插入/删除/获取优先级最高的元素

 3.3 top-k问题


一、优先级队列

1、概念

我们都知道队列队列是一种先进先出(FIFO)的数据结构,但有些情况下,操作的数据可能带有优先级,一般出队列时,可能需要优先级高的元素先出队列,该中场景下,使用队列显然不合适。(例如,我们在用手机玩游戏的时候,有个电话打过来,那么系统应该优先处理打进来的电话)

在这种情况下, 数据结构应该提供两个最基本的操作,一个是返回最高优先级对象,一个是添加新的对象 。这种数据结构就是 优先级队列 (Priority Queue)

2、优先级队列的模拟实现

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

2.1 堆的概念

如果有一个 集合 K = {k0 k1 k2 kn-1} ,把它的所有元素 按完全二叉树的顺序存储方式存储在一个一维数组中 ,并满足: Ki <= K2i+1 Ki<= K2i+2 (Ki >= K2i+1 Ki >= K2i+2) i = 0 1 2… ,则 称为 小堆 ( 或大 ) 将根节点最大的堆叫做最大堆或大根堆,根节点最小的堆叫做最小堆或小根堆。

 堆的性质:

  • 堆中某个节点的值总是不大于或不小于其父节点的值;
  • 堆总是一棵完全二叉树。

 2.2 堆的存储方式

 从堆的概念可知,堆是一棵完全二叉树,因此可以层序的规则采用顺序的方式来高效存储

注意:对于 非完全二叉树,则不适合使用顺序方式进行存储 ,因为为了能够还原二叉树, 空间中必须要存储空节点,就会导致空间利用率比较低

2.3 堆的创建

 2.3.1 堆向下调整
我们来看这一问题,对于集合 { 27,15,19,18,28,34,65,49,25,37 } 中的数据,如果将其创建成堆呢?

我们知道堆是在二叉树的基础上进行了调整,堆的存储结构是将节点按照层序遍历的方式放到一数组中。所以现在我们先把这一集合构造为二叉树的形式,再来用向下调整的方式,构造出堆,这里我们用小根堆

 

仔细观察上图可发现:根节点的左右子树已经完全满足堆的性质,因此只需将根节点向下调整好即可。 

向下过程 ( 以小根堆为例 )
(1)让 parent 标记需要调整的节点, child 标记 parent 的左孩子 ( 注意: parent 如果有孩子一定先是有左孩子 )
(2)如果 parent 的左孩子存在,即 :child < size , 进行以下操作,直到 parent 的左孩子不存在
  • parent右孩子是否存在,若存在,则找到左右孩子中最小的孩子,让child进行标记
  • parent与较小的孩子child比较,如果:
  1. parent小于较小的孩子child,调整结束
  2. 否则:交换parent与较小的孩子child,交换完成之后,由于较大的元素向下移动,可能导致子树不满足堆的性质,因此需要继续向下调整,即parent = childchild = parent*2+1; 然后继续(2)

代码如下:

public void shiftDown(int[] array, int parent) {
        // child先标记parent的左孩子,因为parent可能有左没有右
        int child = 2 * parent + 1;
        int size = array.length;
        while (child < size) {
            // 如果右孩子存在,找到左右孩子中较小的孩子,用child进行标记
            if(child+1 < size && array[child+1] < array[child]){
                child += 1;
            }
            // 如果双亲比其最小的孩子还小,说明该结构已经满足堆的特性了
            if (array[parent] <= array[child]) {
                break;
            }else{
                // 将双亲与较小的孩子交换
                int t = array[parent];
                array[parent] = array[child];
                array[child] = t;
                // parent中大的元素往下移动,可能会造成子树不满足堆的性质,因此需要继续向下调整
                parent = child;
                child = parent * 2 + 1;
            }
        }
    }
注意:在调整以parent为根的二叉树时,必须要满足parent的左子树和右子树已经是堆了才可以向下调整。
时间复杂度分析:
最坏的情况 即图示的情况, 从根一路比较到叶子,比较的次数为完全二叉树的高度,即时间复杂度为O(logn).
2.3.2 堆的创建

 那对于普通的序列{ 1,5,3,8,7,6 },即根节点的左右子树不满足堆的特性,又该如何调整呢?

 此时可以找倒数第一个非叶子节点,从该节点位置开始往前一直到根节点,遇到一个节点,应用向下调整。

 代码如下:

public static void createHeap(int[] array) {
// 找倒数第一个非叶子节点,从该节点位置开始往前一直到根节点,遇到一个节点,应用向下调整
        int root = ((array.length-2)>>1);  //(array.length-1-1)/2
        for (; root >= 0; root--) {
            shiftDown(array, root); // shiftDown方法在创建大根堆时和小根堆不一样,注意
        }
    }

我们来看一下创建大根堆的例子:

建堆的时间复杂度为O(N).

2.4 堆的插入与删除

2.4.1 堆的插入
堆的插入总共需要两个步骤:
  1. 先将元素放入到底层空间中(注意:空间不够时需要扩容)
  2. 将最后新插入的节点向上调整,直到满足堆的性质

 可以以下图参考该过程:

代码(大根堆为例):

public void shiftUp(int child) {
        // 找到child的双亲
        int parent = (child - 1) / 2;
        while (child > 0) {
            // 如果双亲比孩子大,parent满足堆的性质,调整结束
            if (array[parent] > array[child]) {
                break;
            }
            else{
                // 将双亲与孩子节点进行交换
                int t = array[parent];
                array[parent] = array[child];
                array[child] = t;
                // 小的元素向下移动,可能到值子树不满足对的性质,因此需要继续向上调增
                child = parent;
                parent = (child - 1) / 2;
            }
        }
    }
2.4.2 堆的删除  
注意:堆的删除一定删除的是堆顶元素
具体如下:
  1. 将堆顶元素对堆中最后一个元素交换
  2. 将堆中有效数据个数减少一个
  3. 对堆顶元素进行向下调整

如下图:

2.5 用堆模拟实现优先级队列 

public class MyPriorityQueue {
        // 演示作用,不再考虑扩容部分的代码
        private int[] array = new int[100];
        private int size = 0;
        public void offer(int e) {
            array[size++] = e;
            shiftUp(size - 1);
        }
        public int poll() {
            int oldValue = array[0];
            array[0] = array[--size];
            shiftDown(0);
            return oldValue;
        }
        public int peek() {
            return array[0];
        }
    }

3.常用接口介绍

3.1 PriorityQueue的特性

Java 集合框架中提供了 PriorityQueue PriorityBlockingQueue 两种类型的优先级队列, PriorityQueue 是线程不安全的, PriorityBlockingQueue 是线程安全的。
关于 PriorityQueue 的使用要注意:
1. 使用时必须导入 PriorityQueue 所在的包,即
import java . util . PriorityQueue ;
2. PriorityQueue 中放置的 元素必须要能够比较大小,不能插入无法比较大小的对象,否则会抛出
ClassCastException异常
3. 不能 插入 null 对象,否则会抛出 NullPointerException
4. 没有容量限制,可以插入任意多个元素, 其内部可以自动扩容
5. 插入和删除元素的时间复杂度为 O(logN)
6. PriorityQueue 底层使用了堆数据结构
7. PriorityQueue 默认情况下是 小堆 --- 即每次获取到的元素都是最小的元素

3.2 PriorityQueue常用接口介绍

1. 优先级队列的构造
构造器 功能介绍
PriorityQueue() 创建一个空的优先级队列,默认容量是11
PriorityQueue(int initialCapacity)
创建一个初始容量为 initialCapacity 的优先级队列,注意:
initialCapacity 不能小于 1 ,否则会抛 IllegalArgumentException
PriorityQueue(Collection<?
extends E> c)
用一个集合来创建优先级队列
 static void TestPriorityQueue(){
        // 创建一个空的优先级队列,底层默认容量是11
        PriorityQueue<Integer> q1 = new PriorityQueue<>();
        // 创建一个空的优先级队列,底层的容量为initialCapacity
        PriorityQueue<Integer> q2 = new PriorityQueue<>(100);
        ArrayList<Integer> list = new ArrayList<>();
        list.add(4);
        list.add(3);
        list.add(2);
        list.add(1);
        // 用ArrayList对象来构造一个优先级队列的对象
        // q3中已经包含了三个元素
        PriorityQueue<Integer> q3 = new PriorityQueue<>(list);
        System.out.println(q3.size());
        System.out.println(q3.peek());
    }

 注意:默认情况下,PriorityQueue队列是小堆,如果需要大堆需要用户提供比较器

 // 用户自己定义的比较器:直接实现Comparator接口,然后重写该接口中的compare方法即可
    class IntCmp implements Comparator<Integer>{
        @Override
        public int compare(Integer o1, Integer o2) {
            return o2-o1;
        }
    }
    public class TestPriorityQueue {
        public static void main(String[] args) {
            PriorityQueue<Integer> p = new PriorityQueue<>(new IntCmp());
            p.offer(4);
            p.offer(3);
            p.offer(2);
            p.offer(1);
            p.offer(5);
            System.out.println(p.peek());
        }
    }
此时创建出来的就是一个大堆。
2. 插入/删除/获取优先级最高的元素
函数名 功能介绍
boolean offer(E e)
插入元素 e ,插入成功返回 true ,如果 e 对象为空,抛出 NullPointerException 异常,时 间复杂度 O(logN), 注意:空间不够时候会进行扩容
E peek() 获取优先级最高的元素,如果优先级队列为空,返回null
E poll() 移除优先级最高的元素并返回,如果优先级队列为空,返回null
int size() 获取有效元素的个数
void clear()
清空
boolean
isEmpty()
检测优先级队列是否为空,空返回true
优先级队列的扩容说明:
  • 如果容量小于64时,是按照oldCapacity2倍方式扩容的
  • 如果容量大于等于64,是按照oldCapacity1.5倍方式扩容的
  • 如果容量超过MAX_ARRAY_SIZE,按照MAX_ARRAY_SIZE来进行扩容

 3.3 top-k问题

 top-k问题:最大或者最小的前k个数据。

 题目链接:https://leetcode.cn/problems/smallest-k-lcci/description/icon-default.png?t=N7T8https://leetcode.cn/problems/smallest-k-lcci/description/代码:

class Solution {
        public int[] smallestK(int[] arr, int k) {
            // 参数检测
            if(null == arr || k <= 0)
                return new int[0];
            PriorityQueue<Integer> q = new PriorityQueue<>(arr.length);
            // 将数组中的元素依次放到堆中
            for(int i = 0; i < arr.length; ++i){
                q.offer(arr[i]);
            }
            // 将优先级队列的前k个元素放到数组中
            int[] ret = new int[k];
            for(int i = 0; i < k; ++i){
                ret[i] = q.poll();
            }
            return ret;
        }
    }

 该解法只是PriorityQueue的简单使用,并不是topK最好的做法。

对于 Top-K 问题,能想到的最简单直接的方式就是排序,但是:如果数据量非常大,排序就不太可取了 ( 可能数据都不能一下子全部加载到内存中 ) 。最佳的方式就是用堆来解决,基本思路如下:
1. 用数据集合中前 K 个元素来建堆
前k个最大的元素,则建小堆
前k个最小的元素,则建大堆
2. 用剩余的 N-K 个元素依次与堆顶元素来比较,不满足则替换堆顶元素
将剩余 N-K 个元素依次与堆顶元素比完之后,堆中剩余的 K 个元素就是所求的前 K 个最小或者最大的元素。

代码:

//使用比较器创建大根堆
class comp 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[] ret = new int[k];
        if(arr == null || k <= 0) {
            return ret;
        }
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(new comp());
        for (int i = 0;i < k ;i++) {
            priorityQueue.offer(arr[i]);
        }
        for (int i = k;i < arr.length;i++) {
            int top = priorityQueue.peek();
            if (arr[i] < top) {
                priorityQueue.poll();
                priorityQueue.offer(arr[i]);
            }
        }
        int[] res = new int[k];
        for (int i = 0; i < k;i++) {
            res[i] = priorityQueue.poll();
        }
        return res;
    }
}

 对堆的内容就先介绍到这儿了,希望能帮到你呀!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/478156.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

WebGIS管线在线编辑器(电力、水力、燃气、热力、热能管线)

随着GIS等信息技术的发展&#xff0c;地下管线管理也从二维平面向三维立体管理迈进。传统管线信息管理系统将管线及其附属设施抽象成二维平面内的点、要素&#xff0c;并使用各类点符号、不同颜色线段进行表达。虽能一定程度上满足城市智慧运行的需要&#xff0c;但不能很直观的…

51单片机学习笔记6 数码管显示

51单片机学习笔记5 数码管显示 一、动态数码管1. 动态数码管工作原理2. 工作过程3. 原理图&#xff08;1&#xff09;数码管及74HC245&#xff08;2&#xff09;74HC138译码器 4. 74HC245介绍&#xff08;1&#xff09;**功能**&#xff08;2&#xff09;**引脚**&#xff08;3…

unity3d——沙盒路径

文章目录 Unity3D中不同平台的沙盒路径&#xff1a; 示例 在Unity3D中&#xff0c;尤其是在移动平台如Android和iOS上&#xff0c;由于系统安全机制&#xff0c;应用程序不能直接访问操作系统的所有文件和目录&#xff0c;而是被限制在一个特定的“沙盒”环境中。这个沙盒是一个…

迷宫(蓝桥杯)——DFS和BFS

迷宫 题目描述 下图给出了一个迷宫的平面图&#xff0c;其中标记为 1 的为障碍&#xff0c;标记为 0 的为可以通行的地方。 010000 000100 001001 110000迷宫的入口为左上角&#xff0c;出口为右下角&#xff0c;在迷宫中&#xff0c;只能从一个位置走到这 个它的上、下、左…

【Linux】Centos7安装redis

目录 下载安装包安装1.解压2.环境安装3.查看redis的安装路径4.将之前redis的配置文件&#xff0c;复制到安装路径下&#xff08;新建一个文件夹并复制&#xff09;5.redis 设置默认后台启动&#xff0c;修改配置文件6.启动redis服务默认启动通过配置文件启动查看进程 7.开放637…

52、Qt/窗口、常用类、ui相关学习20240321

一、使用Qt 自由发挥登录窗口的应用场景&#xff0c;实现一个登录窗口界面。 要求&#xff1a; 1. 需要使用Ui界面文件进行界面设计 2. ui界面上的组件相关设置&#xff0c;通过代码实现 3. 需要添加适当的动图。 代码&#xff1a; #include "widget.h" #incl…

【重温设计模式】访问者模式及其Java示例

访问者模式的基本概念 访问者模式&#xff0c;一种行为型设计模式&#xff0c;其基本定义是&#xff1a;允许一个或者多个操作应用到一组对象上&#xff0c;解耦操作和对象的具体类&#xff0c;使得操作的添加可以独立于对象的类结构变化。在面向对象编程中&#xff0c;访问者…

软件推荐 篇三十七:开源免费无广告的在线音乐免费播放 | MusicFree纯净无广告体验-小众冷门推荐

引言 自从QQ音乐没了杰伦、某云开始收费&#xff0c;除了各种广告弹窗导致电脑卡的要死&#xff0c;打工人就靠这点音乐背景熬夜了&#xff0c;木有办法&#xff0c;得有个开源免费的听歌软件吧&#xff0c;一搜github&#xff0c;软件一大堆&#xff0c;作为一个打工仔&#…

八大排序算法之希尔排序

希尔排序是插入排序的进阶版本&#xff0c;他多次调用插入排序&#xff0c;在插入排序上进行了改造&#xff0c;使其处理无序的数据时候更快 核心思想&#xff1a;1.分组 2.直接插入排序&#xff1a;越有序越快 算法思想&#xff1a; 间隔式分组&#xff0c;利用直接插入排序…

java数据结构与算法刷题-----LeetCode215. 数组中的第K个最大元素

java数据结构与算法刷题目录&#xff08;剑指Offer、LeetCode、ACM&#xff09;-----主目录-----持续更新(进不去说明我没写完)&#xff1a;https://blog.csdn.net/grd_java/article/details/123063846 文章目录 解题思路&#xff1a;时间复杂度O( n n n)&#xff0c;空间复杂度…

【深度学习】训练Stable Diffusion环境

仓库&#xff1a; https://github.com/bmaltais/kohya_ss.git 基础镜像&#xff1a; from kevinchina/deeplearning:sdxllighting_trt_nginx_002api docker run --net host --gpus device0 -e APIWORKS1 -it t1:t1 bash构建环境&#xff1a; sudo -i git clone https://git…

算法第三十一天-直方图的水量

直方图的水量 题目要求 解题思路 使用面向列的计算比面向行的计算更加容易。我们只需要考虑当前的位置的左右最高模板的高度。 方法一、暴力解法 每个位置能接到多少雨水&#xff0c;很容易想到[木桶效应]&#xff0c;即是由两边最短的木板限制的。那么直观思路就是&#x…

C语言 动态内存管理

目录 前言 一、动态内存分配 二、malloc和free函数 2.1 malloc函数 2.2 free函数 三、calloc和realloc函数 3.1 calloc函数 3.2 realloc函数 四、常见的动态内存的错误 1.对NULL指针的解引用操作 2.对动态开辟空间的越界访问 3.对非动态开辟内存使用free释放 4.使用…

深度学习-2.8模型拟合概念和欠拟合模型、过拟合调整策略

模型拟合概念和欠拟合模型、过拟合调整策略 文章目录 模型拟合概念和欠拟合模型、过拟合调整策略一、模型拟合度概念介绍1.测试集的“不可知悖论”2.模型拟合度概念与实验 二、过拟合、欠拟合问题解决方案1. 欠拟合解决方案2.过拟合解决方案 三、神经网络结果选择策略1. 参数和…

拼多多2023年实现营收2476亿 助力品质好物与消费升级双向奔赴

拼多多集团近日发布了截至去年12月31日的财务业绩报告&#xff0c;拼多多在2023年第四季度实现了889亿元的营收&#xff0c;同比增长了惊人的123%。而在全年范围内&#xff0c;拼多多的营收更是高达2476亿元&#xff0c;同比增长了90%。 去年是拼多多全面拥抱高质量发展的元年…

晶体管图示仪 能测 IGBT. Mosfet. Diode. BJT......

STD2000晶体管图示仪系统能测试很多电子元器件的静态直流参数&#xff08;如击穿电压V(BR)CES/V(BR)DSs、漏电流ICEs/lGEs/IGSs/lDSs、阈值电压/VGE(th)、开启电压/VCE(on)、跨导/Gfe/Gfs、压降/Vf、导通内阻Rds(on)&#xff09;。 测试种类覆盖 7 大类别26分类&#xff0c;包…

解锁企业数字化运营管理:论专业数据中台解决方案的重要性-亿发

没有数据中台&#xff0c;数字化经营就像是建立在沙滩上的城堡&#xff0c;缺乏坚实的基础支撑。数据中台对于企业数字化经营能力的建设至关重要&#xff0c;它扮演着连接、整合和管理数据的关键角色&#xff0c;出现将扩展企业可利用数据的范围。传统的业务分析主要使用财务数…

Python使用PaddleOCR进行图片转文字

PaddleOCR是百度飞桨开发的OCR库 安装 安装PaddleOCR&#xff0c;只需要两个命令&#xff1a; pip install paddlepaddle2.4.2 pip install paddleocr 基本使用 PaddleOCR的使用也很简单&#xff1a; from paddleocr import PaddleOCR# use_angle_cls&#xff1a;是否使用…

高通 8255 基本通信(QUP)Android侧控制方法说明

一&#xff1a;整体说明 高通8255芯片中&#xff0c;SPI IIC UART核心统一由QUP V3 进行控制 QUP V3为可编程模块&#xff0c;可以将不同通道配置为SPI IIC UART通路&#xff0c;此部分配置在QNX侧 QUP 资源可以直接被QNX使用&#xff0c;Android侧可以通过两种方法使用QUP资源…

Android Audio相关

AudioManager AudioService的Bp端&#xff0c;调用AudioManager>AudioService&#xff08;代码实现&#xff09; AudioService 继承自IAudioService.Stub&#xff0c;为Bn端 AudioSystem AudioService功能实现都依赖于AudioSystem&#xff0c;AudioService通过AudioSys…