【数据结构】堆(创建,调整,插入,删除,运用)

目录

堆的概念:

堆的性质:

堆的存储方式:

堆的创建 : 

堆的调整:

向下调整:

向上调整:

堆的创建:

建堆的时间复杂度:

 向下调整:

向上调整:

堆的插入与删除:

 堆的插入:

堆的删除:

堆的应用:

1.PriorityQueue的实现

2.堆排序:

3.Top-k问题 

结语:


堆的概念:

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

堆的性质:

(1)堆中某个节点的值总是不大于(大根堆)或不小于(小根堆)其父节点的值。

(2)堆总是一棵完全二叉树。

具体如下图。 

 

堆的存储方式:

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

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

将元素存储到数组中后,可以根据二叉树章节的性质对树进行还原。假设i为节点在数组中的下标,则有:

(1)如果i为0,则i表示的节点为根节点,否则i节点的双亲节点为 (i - 1)/2.

(2)如果2 * i + 1 小于节点个数,则节点i的左孩子下标为2 * i + 1,否则没有左孩子。

(3)如果2 * i + 2 小于节点个数,则节点i的右孩子下标为2 * i + 2,否则没有右孩子。

堆的创建 : 

为了使文章可读性更高下面给出测试堆类的基本代码,下面文章给出的代码均围绕这上面来。

elem:是一个类里面的数组(方便后序操作)

usedSize:是记录数组里面有多少个元素(不是数组容量)

TestHeap:构造方法为了简便把数组容量设为10,大小可以自己调整

initElem:初始化

public class TestHeap {public int[] elem;public int usedSize;public TestHeap(){elem = new int[10];}public void initElem(int[] array){for(int i = 0;i < array.length;i++){elem[i] = array[i];usedSize++;}}
}

堆的调整:

堆有向上调整向下调整两种调整方式,在创建时我们采用向下调整方式,这样的时间复杂度比较低。故下面主要讲解向下过程(以大堆为例) 步骤如下:

向下调整:

1. 让parent标记需要调整的节点,child标记parent的左孩子(注意:parent如果有孩子一定先是有左孩子)。

2. 如果parent的左孩子存在,即:child < size, 进行以下操作,直到parent的左孩子不存在。

(1)parent右孩子是否存在,存在找到左右孩子中最小的孩子,让child进行标记。

(2)将parent与较小的孩子child比较,如果:

a:parent小于较小的孩子child,调整结束。

b:否则:交换parent与较小的孩子child,交换完成之后,parent中大的元素向下移动,可能导致子 树不满足对的性质,因此需要继续向下调整,即parent = child;child = parent*2+1; 然后继续。

 以数组{ 27,15,19,18,28,34,65,49,25,37 }为例调整完变成。

对应的代码如下:

如果想要转换成小堆的话把大于号小于号改一改即可,故下面不在过多描述。

private void siftDown1(int parent,int end){int child = parent*2+1;while(child < end){if(child+1 < usedSize && elem[child] < elem[child+1]){child++;}if(elem[child] > elem[parent]){swap(child,parent);parent = child;child = parent*2+1;}else{break;}}}

 为了使代码整洁故再实现一个swap方法。

private void swap(int i,int j){int tmp = elem[i];elem[i] = elem[j];elem[j] = tmp;}

注意:在调整以parent为根的二叉树时,必须要满足parent的左子树和右子树已经是堆了才可以向下调整。 时间复杂度分析:最坏的情况即图示的情况,从根一路比较到叶子,比较的次数为完全二叉树的高度,即时间复杂度为O(logn)log下标是以2为底的。

向上调整:

具体过程如图(按照插入的80走的路径):

代码如下:

先找新结点的parent的下标再child大于0的情况下循环进行比较交换,一旦发现不满足条件的立刻跳出循环,因为在使用向上调整之前堆已经排序好了。

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

堆的创建:

如图所示是从最后一个结点的父亲结点开始遍历每一个结点都调用siftdown1进行向下调整,之后不断减减直到小于0(下标)。

代码如下:

 public void createBigHeap(){for(int parent = (usedSize-1-1)/2;parent >= 0;parent--){siftDown1(parent,usedSize);}}

运行结果:

通过观察elem的元素我们可以发现向下调整成功。💖

建堆的时间复杂度:

 向下调整:

因为堆是完全二叉树,而满二叉树也是完全二叉树,此处为了简化使用满二叉树来证明(时间复杂度本来看的就是 近似值,多几个节点不影响最终结果):如图:

向上调整:

如图:

经过比较我们选择时间复杂度较低的来进行堆的创建即向下调整,至于向上调整我们用于堆的堆的插入与删除。

堆的插入与删除:

 堆的插入:

堆的插入总共需要两个步骤:

(1)先将元素放入到底层空间中(注意:空间不够时需要扩容).

(2)将最后新插入的节点向上调整,直到满足堆的性质.

代码如下:

isFull用来判断是否需要扩容

public boolean isFull(){return usedSize == elem.length;}

siftUp用来向上调整,先找到新参数的parent结点, 传入siftup的参数为新offer进来的参数。

 public void offer(int val){//1.判断满if(isFull()){this.elem = Arrays.copyOf(elem,elem.length*2);}elem[usedSize] = val;usedSize++;siftUp(usedSize-1);}

运行结果如下:

我们可以发现成功增加数据并完成排序。

堆的删除:

注意:堆的删除一定删除的是堆顶元素。具体如下:

(1) 将堆顶元素对堆中最后一个元素交换。

(2) 将堆中有效数据个数减少一个。

(3)对堆顶元素进行向下调整 。

 代码如下:

其实就是把最后一个元素的空间腾出来。

public int poll(){int tmp = elem[0];swap(0,usedSize-1);usedSize--;siftDown1(0,usedSize);return tmp;}

运行结果如下:

可以看到65被成功删除并且数组的序列没有改变

堆的应用:

1.PriorityQueue的实现

可以使用堆来实现优先队列,由于java语言有自带的优先队列故这里不在实现给出它的常用方法直接调用即可。

函数名功能介绍
boolean offer(E e)插入元素e,插入成功返回true,如果e对象为空,抛出NullPointerException异常,注意:空间不够时候会进行扩容
E peek()获取优先级最高的元素,如果优先级队列为空,返回null
E poll()移除优先级最高的元素并返回,如果优先级队列为空,返回null
int size()获取有效元素的个数
void clear()清空
boolean isEmpty()检测优先级队列是否为空,空返回true

2.堆排序:

堆排序即利用堆的思想来进行排序,总共分为两个步骤:

1. 建堆

升序:建大堆

降序:建小堆

2. 利用堆删除思想来进行排序

建堆和堆删除中都用到了向下调整,因此掌握了向下调整,就可以完成堆排序。

具体过程如下:

代码后序会将8大排序整理成一篇排序专项。

3.Top-k问题 

TOP-K问题:即求数据集合中前K个最大的元素或者最小的元素,一般情况下数据量都比较大。

比如:专业前10名、世界500强、富豪榜、游戏中前100的活跃玩家等。 对于Top-K问题,能想到的最简单直接的方式就是排序,但是:如果数据量非常大,排序就不太可取了(可能数据都 不能一下子全部加载到内存中)。最佳的方式就是用堆来解决,基本思路如下:

1. 用数据集合中前K个元素来建堆

(1)前k个最大的元素,则建小堆.

(2)前k个最小的元素,则建大堆。

2. 用剩余的N-K个元素依次与堆顶元素来比较,不满足则替换堆顶元素

将剩余N-K个元素依次与堆顶元素比完之后,堆中剩余的K个元素就是所求的前K个最小或者最大的元素。

不要用Arrays.sort来做这道题,因为这是一道面试题,用sort就可以快速结束面试,回家等通知了。

top-k问题

使用堆的AC优化代码:

class Imp implements Comparator<Integer>{@Overridepublic int compare(Integer o1,Integer o2){return o2.compareTo(o1);}}
class Solution {public int[] smallestK(int[] arr, int k) {Imp imp = new Imp();PriorityQueue<Integer> priorityqueue = new PriorityQueue<>(imp);int[] ans = new int[k];if(k == 0){return ans;}for(int i = 0;i < k; i++){priorityqueue.offer(arr[i]);}for(int i = k;i < arr.length; i++){int tmp = priorityqueue.peek();if(arr[i] < tmp){priorityqueue.poll();priorityqueue.offer(arr[i]);}}for(int i = 0;i < k; i++){ans[i] = priorityqueue.poll();}return ans;}
}

结语:

其实写博客不仅仅是为了教大家,同时这也有利于我巩固自己的知识点,和一个学习的总结,由于作者水平有限,对文章有任何问题的还请指出,接受大家的批评,让我改进,如果大家有所收获的话还请不要吝啬你们的点赞收藏和关注,这可以激励我写出更加优秀的文章。

 

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

红队打靶练习:GLASGOW SMILE: 1.1

目录 信息收集 1、arp 2、nmap 3、nikto 4、whatweb 目录探测 1、gobuster 2、dirsearch WEB web信息收集 /how_to.txt /joomla CMS利用 1、爆破后台 2、登录 3、反弹shell 提权 系统信息收集 rob用户登录 abner用户 penguin用户 get root flag 信息收集…

HARRYPOTTER: FAWKES

攻击机 192.168.223.128 目标机192.168.223.143 主机发现 nmap -sP 192.168.223.0/24 端口扫描 nmap -sV -p- -A 192.168.223.143 开启了21 22 80 2222 9898 五个端口&#xff0c;其中21端口可以匿名FTP登录&#xff0c;好像有点说法,百度搜索一下发现可以用anonymous登录…

网络安全产品之认识准入控制系统

文章目录 一、什么是准入控制系统二、准入控制系统的主要功能1. 接入设备的身份认证2. 接入设备的安全性检查 三、准入控制系统的工作原理四、准入控制系统的特点五、准入控制系统的部署方式1. 网关模式2. 控制旁路模式 六、准入控制系统的应用场景七、企业如何利用准入控制系统…

使用PDFBox实现pdf转其他图片格式

最近在做一个小项目&#xff0c;项目中有一个功能要把pdf格式的图片转换为其它格式&#xff0c;接下来看看用pdfbox来如何实现吧。 首先导入pdfbox相关依赖&#xff1a; <dependency> <groupId>org.apache.pdfbox</groupId> <artifactId>pdfbox</a…

【高阶数据结构】位图布隆过滤器

文章目录 1. 位图1.1什么是位图1.2为什么会有位图1.3 实现位图1.4 位图的应用 2. 布隆过滤器2.1 什么是布隆过滤器2.2 为什么会有布隆过滤器2.3 布隆过滤器的插入2.4 布隆过滤器的查找2.5 布隆过滤器的模拟实现2.6 布隆过滤器的优点2.7 布隆过滤器缺陷 3. 海量数据面试题3.1 哈…

CTFshow web(命令执行29-36)

?ceval($_GET[shy]);&shypassthru(cat flag.php); #逃逸过滤 ?cinclude%09$_GET[shy]?>&shyphp://filter/readconvert.base64-encode/resourceflag.php #文件包含 ?cinclude%0a$_GET[cmd]?>&cmdphp://filter/readconvert.base64-encode/…

Kubernetes实战(二十七)-HPA实战

1 HPA简介 HPA 全称是 Horizontal Pod Autoscaler&#xff0c;用于POD 水平自动伸缩&#xff0c; HPA 可以 基于 POD CPU 利用率对 deployment 中的 pod 数量进行自动扩缩容&#xff08;除了 CPU 也可以基于自定义的指标进行自动扩缩容&#xff09;。pod 自动缩放不适用于无法…

ubuntu22.04@laptop OpenCV Get Started: 001_reading_displaying_write_image

ubuntu22.04laptop OpenCV Get Started: 001_reading_displaying_write_image 1. 源由2. Read/Display/Write应用Demo2.1 C应用Demo2.2 Python应用Demo 3. 过程分析3.1 导入OpenCV库3.2 读取图像文件3.3 显示图像3.4 保存图像文件 4. 总结5. 参考资料 1. 源由 读、写、显示图像…

Windows - URL Scheme - 在Windows上无管理员权限为你的程序添加URL Scheme

Windows - URL Scheme - 在Windows上无管理员权限为你的程序添加URL Scheme What 想不想在浏览器打开/控制你的电脑应用&#xff1f; 比如我在浏览器地址栏输入wegame://后回车会提示是否打开URL:wegame Portocol。 若出现了始终允许选项&#xff0c;你甚至可以写一个Web界面…

【AIGC核心技术剖析】DreamCraft3D一种层次化的3D内容生成方法

DreamCraft3D是一种用于生成高保真、连贯3D对象的层次化3D内容生成方法。它利用2D参考图像引导几何塑造和纹理增强阶段&#xff0c;通过视角相关扩散模型执行得分蒸馏采样&#xff0c;解决了现有方法中存在的一致性问题。使用Bootstrapped Score Distillation来提高纹理&#x…

React 实现表单组件

表单是html的基础元素&#xff0c;接下来我会用React实现一个表单组件。支持包括输入状态管理&#xff0c;表单验证&#xff0c;错误信息展示&#xff0c;表单提交&#xff0c;动态表单元素等功能。 数据状态 表单元素的输入状态管理&#xff0c;可以基于react state 实现。 …

计算机网络——04接入网和物理媒体

接入网和物理媒体 接入网络和物理媒体 怎样将端系统和边缘路由器连接&#xff1f; 住宅接入网络单位接入网络&#xff08;学校、公司&#xff09;无线接入网络 住宅接入&#xff1a;modem 将上网数据调制加载到音频信号上&#xff0c;在电话线上传输&#xff0c;在局端将其…

Ubuntu22.04 gnome-builder gnome C 应用程序习练笔记(一)

一、序言 gnome-builder构建器是gnome程序开发的集成环境&#xff0c;支持主力语言C, C, Vala, jscript, python等&#xff0c;界面以最新的 gtk 4.12 为主力&#xff0c;将其下版本的gtk直接压入了depreciated&#xff0c;但gtk4.12与普遍使用的gtk3有很大区别&#xff0c;原…

Java stream 流的基本使用

Java stream 的基本使用 package com.zhong.streamdemo.usestreamdemo;import jdk.jfr.DataAmount; import lombok.AllArgsConstructor; import lombok.Data; import lombok.NoArgsConstructor;import java.util.ArrayList; import java.util.Comparator; import java.util.Li…

elasticsearch重置密码操作

安装es的时候需要测试这个url&#xff1a;http://127.0.0.1:9200/ 出现弹窗让我输入账号和密码。我第一次登录&#xff0c;没有设置过账号和密码&#xff0c; 解决方法是&#xff1a;在es的bin目录下打开cmd窗口&#xff0c;敲命令&#xff1a;.\elasticsearch-reset-password…

Docker 搭建mysql 集群(二)

PXC方案 很明显 PXC方案在任何一个节点写入的数据都会同步到其他节点&#xff0c;数据双向同步的&#xff08;在任何节点上都可以同时读写&#xff09; 创建MySQL PXC集群 1 安装PXC镜像 docker pull percona/percona-xtradb-cluster:5.7.21 2 为PXC镜像改名 docker tag pe…

【开源】基于JAVA+Vue+SpringBoot的新能源电池回收系统

目录 一、摘要1.1 项目介绍1.2 项目录屏 二、功能模块2.1 用户档案模块2.2 电池品类模块2.3 回收机构模块2.4 电池订单模块2.5 客服咨询模块 三、系统设计3.1 用例设计3.2 业务流程设计3.3 E-R 图设计 四、系统展示五、核心代码5.1 增改电池类型5.2 查询电池品类5.3 查询电池回…

代码随想录算法训练营第四十六天(动态规划篇)|01背包(滚动数组方法)

01背包&#xff08;滚动数组方法&#xff09; 学习资料&#xff1a;代码随想录 (programmercarl.com) 题目链接&#xff08;和上次一样&#xff09;&#xff1a;题目页面 (kamacoder.com) 思路 使用一维滚动数组代替二维数组。二维数组的解法记录在&#xff1a;代码随想录算…

【Linux】进程学习(一):基本认识

目录 1.基本概念2.初步理解3.描述进程-PCB3.1task_struct-PCB的一种3.2task_ struct内容分类 4.组织进程5.查看进程5.1通过ps指令查看5.2通过系统目录查看 6.通过系统调用获取进程的PID和PPID7.通过系统调用创建进程-fork初识 1.基本概念 课本概念&#xff1a;程序的一个执行实…

Linux---线程

线程概念 在一个程序里的一个执行路线就叫做线程&#xff08;thread&#xff09;。更准确的定义是&#xff1a;线程是“一个进程内部的控制序列” 一切进程至少都有一个执行线程 线程在进程内部运行&#xff0c;本质是在进程地址空间内运行 在Linux系统中&#xff0c;在CPU眼中…