模拟堆-java

模拟堆也是对堆的一次深入理解和一些其它操作，可以了解一下。

文章目录

前言

一、模拟堆

二、算法思路

1.结点上移

2.结点下移

3.插入一个数

 4.输出当前集合的最小值

5.删除当前集合的最小值（数据保证此时的最小值唯一）

6.删除第k个插入的数

7.修改第k个插入的数，修改为x

三、代码如下

1.代码如下：

2.读入数据：

3.代码运行结果

总结

前言

模拟堆也是对堆的一次深入理解和一些其它操作，可以了解一下。

提示：以下是本篇文章正文内容，下面案例可供参考

一、模拟堆

维护一个集合，初始时集合为空，支持如下几种操作：

  1. I x，插入一个数 x；
  2. PM，输出当前集合中的最小值；
  3. DM，删除当前集合中的最小值（数据保证此时的最小值唯一）；
  4. D k，删除第 k 个插入的数；
  5. C k x，修改第 k 个插入的数，将其变为 x；

现在要进行 N 次操作，对于所有第 22 个操作，输出当前集合的最小值。

输入格式

第一行包含整数 N。

接下来 N 行，每行包含一个操作指令，操作指令为 I x，PM，DM，D k 或 C k x 中的一种。

输出格式

对于每个输出指令 PM，输出一个结果，表示当前集合中的最小值。

每个结果占一行。

数据范围

1≤N≤100000
−1000000000≤x≤1000000000
数据保证合法。

二、算法思路

我们还是通过一维整型数组heap来存储堆的值，数组下标来表示是哪一个结点，size表示堆中结点的个数或者堆中最后一个元素的下标。这道题中我们还是以小根堆为例子。堆在数组中存储，任一结点的下标为x，那么它的左孩子在数组中存储的下标为2x，右孩子在数组中存储的下标为2x + 1。（注：数组存储结点下标从1开始）

1.结点上移

当我们插入一个新结点这个结点值比它的父结点值小或者修改某一个结点结点值比它的父节点小这两种情况我们才会让结点上移来维护小根堆的性质。

    //结点上移，只需要跟父结点比较即可
    public static void up(int x){
        while ( x / 2 >= 1 && heap[x / 2] > heap[x]){
            int temp = heap[x / 2];
            heap[x / 2] = heap[x];
            heap[x] = temp;
            x /= 2;
        }
    }

我们需要判断当前下标有没有父结点即 x / 2是否满足大于等于1，并且当父结点的值比子结点的值大的时候，我们就需要将父结点和子结点进行交换，然后再判断父结点是否小于它的父节点重复上述过程。具体详情可以看https://blog.csdn.net/m0_63267251/article/details/139388919这篇博客。

2.结点下移

当我们结点值修改后比它的左孩子或者右孩子值大，然后我们从中找到值最小的那个索引，然后让父结点跟最小的结点进行交换，交换后我们再判断当前结点的值是否比它的左孩子或者右孩子值大，重复上述操作，我们要保证父节点的值要小于它的左孩子和右孩子的值。 具体详情可以看https://blog.csdn.net/m0_63267251/article/details/139388919这篇博客。

    //传入结点下标
    public static void down(int x){
        int temp = x;
        //两个if语句来找出3个结点中最小的结点的下标
        if(2 * x <= size && heap[2* x] < heap[temp]){
            temp = 2 * x;
        }
        if (2 * x + 1 <= size && heap[2*x + 1] < heap[temp]){
            temp = 2 * x + 1;
        }
        //说明此时结点不是最小值，进行交换，再递归处理看是否还需要交换
        if(temp != x){
            int t = heap[temp];
            heap[temp] = heap[x];
            heap[x] = t;
            down(temp);
        }
    }

3.插入一个数

插入一个数，我们直接在数组的末尾添加元素即可，而size既可以表示堆中元素的个数，也可以表示堆中元素在数组中存储的最后一个结点的下标。故我们添加元素为heap[size] = x;size++;

             if (cmd.equals("I")){
                x = Integer.parseInt(s[1]);
                heap[++size] = x;
             }

 4.输出当前集合的最小值

因为我们搭建的是小根堆，故我们堆中的根结点的值就是堆中元素的最小值即heap[1];

5.删除当前集合的最小值（数据保证此时的最小值唯一）

我们删除当前集合的最小值，数组的第一个元素是很难被删除的，我们还是删除数组的最后一个元素，将根节点赋值为数组的最后一个元素即heap[1] = heap[size];size--;然后此时有可能小根堆的性质被破坏，所以我们只需要将根节点结点下移操作就可以即down(1)；此时我们就完成了删除当前集合最小值的情况。

6.删除第k个插入的数

这个操作麻烦的是删除第k个插入的数，而不是删除第k个结点。因此我们需要一个一维整型数组khp，来存储第k个插入的数在堆中的下标即khp[k]；我们还需要一个一维整型数组hp，来存储我们堆中的点是第几个插入的点；例如kph[j] = k表示第j个插入的点是堆中第k个结点，ph[k] = j表示堆中的第k个结点时我们第k个插入的点，这两个数组的值对应的是相反的。那么我们就需要更新一下我们的down操作和up操作。

    public static void down(int x){
        int temp = x;
        if(2 * x <= size && heap[2 * x] < heap[temp]){
            temp = 2 * x;
        }
        if(2 * x + 1 <= size && heap[2 * x + 1] < heap[temp]){
            temp = 2 * x + 1;
        }
        if(temp != x){
            hp_swap(temp,x);
            down(temp);
        }
    }
    //结点上移，只需要跟父结点比较即可
    public static void up(int x){
        while ( x / 2 >= 1 && heap[x / 2] > heap[x]){
            hp_swap(x,x/2);
            x /= 2;
        }
    }
    //因为hp数组可以对应为堆中的元素下标在khp数中的关系，所以我们先交换khp，后交换hp或者先交换hp再交换khp也可以
    public static void hp_swap(int a,int b){
        int t = khp[hp[a]];
        khp[hp[a]] = khp[hp[b]];
        khp[hp[b]] = t;
        t = hp[a];
        hp[a] = hp[b];
        hp[b] = t;
        t = heap[a];
        heap[a] = heap[b];
        heap[b] = t;
    }

 对应的插入一个数、输出当前集合和最小值和删除集合最小值操作更新。

            if (cmd.equals("I")){
                x = Integer.parseInt(s[1]);
                size++;
                m++;
                heap[size] = x;
                khp[m] = size;
                hp[size] = m;
                up(size);
            } else if (cmd.equals("PM")) {
                pw.println(heap[1]);
            } else if (cmd.equals("DM")) {
                hp_swap(1,size);
                size--;
                down(1);
            } else if (cmd.equals("D")) {
                k = Integer.parseInt(s[1]);
                //找到第k歌数在堆中的位置
                k = khp[k];
                hp_swap(k,size);
                size--;
                //两个操作最多执行一个
                up(k);
                down(k);
            }

7.修改第k个插入的数，修改为x

我们将插入第k个数在堆中的坐标找到即khp[k]，然后将堆中的值修改为x即heap[khp[k]] = x。然后再维护一下小根堆性质down(kph[k])、up(khp[k])即可。

            if (cmd.equals("C")) {
                k = Integer.parseInt(s[1]);
                x = Integer.parseInt(s[2]);
                k = khp[k];
                heap[k] = x;
                down(k);
                up(k);
            }

三、代码如下

1.代码如下：


import java.util.*;
import java.io.*;
public class 模拟堆 {
    static PrintWriter pw = new PrintWriter(new OutputStreamWriter(System.out));
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StreamTokenizer st = new StreamTokenizer(br);
    static int N = 100010;
    //堆中的数据
    static int[] heap = new int[N];
    static int size = 0;
    //第k个插入数在堆中的下标
    static int[] khp = new int[N];
    //堆中的哪一个点是我们第几个插入的点
    static int[] hp = new int[N];
    public static void main(String[] args) throws Exception{
        Scanner sc = new Scanner(br);
        int n = nextInt();
        //表示第几个插入的数
        int m = 0;
        while (n-- > 0){
            String[] s = nextLine().split(" ");
            String cmd = s[0];
            int x;
            int k;
            if (cmd.equals("I")){
                x = Integer.parseInt(s[1]);
                size++;
                m++;
                heap[size] = x;
                khp[m] = size;
                hp[size] = m;
                up(size);
            } else if (cmd.equals("PM")) {
                pw.println(heap[1]);
            } else if (cmd.equals("DM")) {
                hp_swap(1,size);
                size--;
                down(1);
            } else if (cmd.equals("D")) {
                k = Integer.parseInt(s[1]);
                //找到第k歌数在堆中的位置
                k = khp[k];
                hp_swap(k,size);
                size--;
                //两个操作最多执行一个
                up(k);
                down(k);
            } else if (cmd.equals("C")) {
                k = Integer.parseInt(s[1]);
                x = Integer.parseInt(s[2]);
                k = khp[k];
                heap[k] = x;
                down(k);
                up(k);
            }

        }
        pw.flush();
    }
    public static void down(int x){
        int temp = x;
        if(2 * x <= size && heap[2 * x] < heap[temp]){
            temp = 2 * x;
        }
        if(2 * x + 1 <= size && heap[2 * x + 1] < heap[temp]){
            temp = 2 * x + 1;
        }
        if(temp != x){
            hp_swap(temp,x);
            down(temp);
        }
    }
    //结点上移，只需要跟父结点比较即可
    public static void up(int x){
        while ( x / 2 >= 1 && heap[x / 2] > heap[x]){
            hp_swap(x,x/2);
            x /= 2;
        }
    }
    //因为hp数组可以对应为堆中的元素下标在khp数中的关系，所以我们要先交换khp，后交换hp或者先交换hp再交换khp也可以
    public static void hp_swap(int a,int b){
        int t = khp[hp[a]];
        khp[hp[a]] = khp[hp[b]];
        khp[hp[b]] = t;
        t = hp[a];
        hp[a] = hp[b];
        hp[b] = t;
        t = heap[a];
        heap[a] = heap[b];
        heap[b] = t;
    }

    public static int nextInt()throws Exception{
        st.nextToken();
        return (int)st.nval;
    }
    public static String nextLine()throws Exception{
        return br.readLine();
    }
}

2.读入数据：

8
I -10
PM
I -10
D 1
C 2 8
I 6
PM
DM

3.代码运行结果

-10
6

总结

上述解释了一下模拟堆中的一些基本操作知道题中各个数组的意思，比较长和难以理解，可以多看看梳理一下。

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

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

相关文章

初识STM32单片机-ADC和DMA

初识STM32单片机-ADC和DMA

初识STM32单片机-ADC和DMA 一、ADC(模拟数字转换器)简介二、ADC基本结构三、DMA(直接存储器读取)简介四、DMA框图和基本结构五、DMA应用实例5.1 数据转运DMA5.2 ADC扫描DMA 六、程序编码6.1 ADC单通道-电位器6.2 ADC多通道-电位器和光敏\热敏\反射红外传感器6.3 DMA数据转运6.4…
阅读更多...
代码随想录算法训练Day28|LeetCode93-复原IP地址、LeetCode78-子集问题、LeetCode90-子集2

代码随想录算法训练Day28|LeetCode93-复原IP地址、LeetCode78-子集问题、LeetCode90-子集2

复原IP地址 题目描述 力扣93-复原IP地址 有效 IP 地址 正好由四个整数&#xff08;每个整数位于 0 到 255 之间组成&#xff0c;且不能含有前导 0&#xff09;&#xff0c;整数之间用 . 分隔。 例如&#xff1a;"0.1.2.201" 和 "192.168.1.1" 是 有效 …
阅读更多...
贝锐花生壳DDNS：远程访问数据库，仅需简单3步

贝锐花生壳DDNS：远程访问数据库，仅需简单3步

在当今数字化时代&#xff0c;数据的远程访问和管理变得至关重要。无论是企业还是个人开发者&#xff0c;都需要一种简单、安全的方式来远程访问和管理本地部署的数据库&#xff0c;如MySQL、PostgreSQL、MongoDB等。贝锐花生壳DDNS服务提供了一个完美的解决方案&#xff0c;通…
阅读更多...
【YOLOv10改进[Backbone]】图像修复网络AirNet助力YOLOv10目标检测效果 + 含全部代码和详细修改方式 + 手撕结构图 + 全网首发

【YOLOv10改进[Backbone]】图像修复网络AirNet助力YOLOv10目标检测效果 + 含全部代码和详细修改方式 + 手撕结构图 + 全网首发

本文带来的是图像复原网络AirNet&#xff0c;它由基于对比度的退化编码器( CBDE )和退化引导的恢复网络( DGRN )两个模块组成。可以在一个网络中恢复各种退化图像。AirNet不受损坏类型和级别的先验限制&#xff0c;仅使用观察到的损坏图像进行推理。本文中将使用图像修复网络Ai…
阅读更多...
SCARA机器人中旋转花键的维护和保养方法！

SCARA机器人中旋转花键的维护和保养方法！

作为精密传动元件的一种&#xff0c;旋转花键在工作过程中承受了较大的负荷。在自动化设备上运用广泛&#xff0c;如&#xff1a;水平多关节机械手臂&#xff08;SCARA&#xff09;、产业用机器人、自动装载机、雷射加工机、搬运装置、机械加工中心的ATC装置等&#xff0c;最适…
阅读更多...
R语言安装caret包报错

R语言安装caret包报错

R语言安装caret包报错&#xff1a;Error: package or namespace load failed for ‘caret’ in loadNamespace(i, c(lib.loc, .libPaths()), versionCheck vI[[i]]): 不存在叫‘recipes’这个名字的程辑包 https://rbasics.org/packages/caret-package-in-r/ R版本的问题&…
阅读更多...
什么牌子的洗地机清洁效果强？618热门品牌推荐与详解

什么牌子的洗地机清洁效果强？618热门品牌推荐与详解

近年来&#xff0c;洗地机的销量急剧增长&#xff0c;已成为清洁类家电中销量第二大的产品。其更新迭代速度也非常快&#xff0c;功能和技术层出不穷&#xff0c;许多消费者不知道如何选择合适的型号。为了帮助大家以最少的花费买到清洁力强的洗地机&#xff0c;笔者特意总结了…
阅读更多...
输入法不显示选字框

输入法不显示选字框

期望效果&#xff1a; 当前效果&#xff1a; 啥也没干突然就这样了 原因&#xff1a;需要以兼容性运行微软输入法 一、进入输入法设置 右键输入法小图标 选择设置 二、进入常规设置 三、开启兼容性运行 完&#xff01;
阅读更多...
跨越百亿营收的今世缘，全国化进程仍挑战重重？

跨越百亿营收的今世缘，全国化进程仍挑战重重？

当前&#xff0c;白酒市场正在经历一场深度调整&#xff0c;随着存量时代到来&#xff0c;白酒品牌地位的更替和竞争格局的重构已经展开。这一背景下&#xff0c;今世缘等地方性酒企也正在凭借对区域市场的深耕&#xff0c;展现出较快的成长速度&#xff0c;并希望能借此占领市…
阅读更多...
【JAVA |总结】JAVASE基础大总结（含思维导图）

【JAVA |总结】JAVASE基础大总结（含思维导图）

✨✨谢谢大家捧场&#xff0c;祝屏幕前的小伙伴们每天都有好运相伴左右&#xff0c;一定要天天开心哦&#xff01;✨✨ &#x1f388;&#x1f388;作者主页&#xff1a; &#x1f388;丠丠64-CSDN博客&#x1f388; ✨✨ 帅哥美女们&#xff0c;我们共同加油&#xff01;一起…
阅读更多...
数据动态变化时实现多选及回显

数据动态变化时实现多选及回显

<template><el-dialog title"设置权限" :visible.sync"showDialog" :close-on-click-modal"false" :append-to-body"true" width"800px"><div v-loading"loading"><el-radio-group v-model&…
阅读更多...
TDMQ CKafka 版弹性存储能力重磅上线！

TDMQ CKafka 版弹性存储能力重磅上线！

导语 自 2024年5月起&#xff0c;TDMQ CKafka 专业版支持弹性存储能力&#xff0c;这种产品形态下&#xff0c;存储可按需使用、按量付费&#xff0c;一方面降低消费即删除、存储使用波动大场景下的存储成本&#xff0c;另一方面存储空间理论上无穷大。 TDMQ CKafka 版产品能…
阅读更多...
微服务网关Gateway（上）

微服务网关Gateway（上）

大家好呀&#xff0c;我是苍何。 这年头&#xff0c;大家都在开始卷简历了&#xff0c;我也看了很多同学的简历&#xff0c;其中有一个同学的简历&#xff0c;我印象最为深刻&#xff0c;他的项目经历中&#xff0c;写了自定义 Gateway 过滤器实现统计接口调用耗时&#xff0c…
阅读更多...
【Hive SQL 每日一题】统计各个商品今年销售额与去年销售额的增长率及排名变化

【Hive SQL 每日一题】统计各个商品今年销售额与去年销售额的增长率及排名变化

文章目录 测试数据需求说明需求实现分步解析 测试数据 -- 创建商品表 DROP TABLE IF EXISTS products; CREATE TABLE products (product_id INT,product_name STRING );INSERT INTO products VALUES (1, Product A), (2, Product B), (3, Product C), (4, Product D), (5, Pro…
阅读更多...
什么是研学活动？快速了解

什么是研学活动？快速了解

说起什么是研学活动&#xff0c;其实就是一种结合学习与实地考察、体验的教育方式&#xff0c;旨在通过实践活动深化学生对课堂知识的理解和应用&#xff0c;培养学生的综合素质和创新能力。让学生在亲身体验中学习和成长。当学校宣布即将组织一次研学活动时&#xff0c;孩子们…
阅读更多...
如何批量复制文件名？文件名批量提取的5个工具！（2024新）

如何批量复制文件名？文件名批量提取的5个工具！（2024新）

在数字化时代&#xff0c;我们经常需要处理大量的文件&#xff0c;其中批量复制文件名或批量提取文件名成为一项常见的任务。这不仅可以提高我们的工作效率&#xff0c;还能使文件管理更为有序。本文将介绍五种2024年最新的文件名批量提取工具&#xff0c;帮助你轻松完成文件名…
阅读更多...
手把手教你从0到1开发浏览器插件

手把手教你从0到1开发浏览器插件

使用Chrome插件可以为Chrome浏览器带来一些功能性的扩展&#xff0c;进而提高使用体验&#xff1b;俗话说的好Chrome没插件&#xff0c;香味少一半&#xff0c;Chrome最大的优势还是其支持众多强大好用的扩展程序&#xff1b;今天就来了解一下插件是如何开发的&#xff0c;和普…
阅读更多...
C语言基础——数组（2）

C语言基础——数组（2）

ʕ • ᴥ • ʔ づ♡ど &#x1f389; 欢迎点赞支持&#x1f389; 个人主页&#xff1a;励志不掉头发的内向程序员&#xff1b; 专栏主页&#xff1a;C语言基础&#xff1b; 文章目录 前言 一、二维数组的创建 1.1 二维数组的概念 1.2二维数组的创建 二、二维数组…
阅读更多...
MySQL中获取时间的方法

MySQL中获取时间的方法

大家好&#xff0c;在MySQL数据库开发中&#xff0c;获取时间是一个常见的需求。MySQL提供了多种方法来获取当前日期、时间和时间戳&#xff0c;并且可以对时间进行格式化、计算和转换。 以下是一些常用的MySQL时间函数及其示例&#xff1a; 1、NOW()&#xff1a;用于获取当前…
阅读更多...
汇舟问卷：国外问卷调查怎么样？

汇舟问卷：国外问卷调查怎么样？

互联网的发展为我们提供了无数的赚钱机会&#xff0c;其中不乏一些投资小、易上手的小项目&#xff0c;可以让大家充分的利用起业余的时间&#xff0c;赚到日常工作之外的收入。 ​这些项目不仅操作简单&#xff0c;而且时间灵活&#xff0c;非常适合想要利用闲余时间赚外快的…
阅读更多...
最新文章

Copyright @ 2022~2023