小顶堆在Java中的一种优雅实现

2023-10-23 13:58
文章标签 java 实现 优雅 一种 小顶

本文主要是介绍小顶堆在Java中的一种优雅实现,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

 今天探索TopK问题的时候取得的阶段性成果,记录下来以供翻阅。

/*** 小顶堆/最小堆实现* * @author stephenshen**/
public class MinHeap {// 堆得存储结构:数组private int[] data;/*** 构造方法:传入一个数组,并转换为一个最小堆* * @param data*/public MinHeap(int[] data) {this.data = data;buildHeap();}/*** 将数组转化为最小堆*/private void buildHeap() {//完全二叉树只有数组下标小于或等于 (data.length) / 2 - 1 的元素有孩子结点,遍历这些结点。//比如上面的图中,数组有10个元素, (data.length) / 2 - 1的值为4,a[4]有孩子结点,但a[5]没有//即,从下自上开始堆化(从最下层非叶子节点开始)for (int i = (data.length) / 2 - 1; i >= 0; i--) {heapify(i);}}/*** 从当前节点开始堆化* * @param i*/private void heapify(int i) {// 获取左右节点数组下标int l = left(i);int r = right(i);// 假定的当前节点、左子节点、右子节点中 最小值的下标int smallest = i;// 存在左子节点,且左子节点的值小于当前节点的值if (l < data.length && data[l] < data[i])smallest = l;// 存在右子节点,且右子节点的值小于当前节点的值if (r < data.length && data[r] < data[i])smallest = r;// 左右结点的值都大于根节点,直接returnif (i == smallest)return;// 将最小值与当前节点互换位置swap(i, smallest);// 从之前最小值节点位置重新堆化heapify(smallest);}/*** 获取右节点的数组下标* * @param i* @return*/private int right(int i) {return (i + 1) << 1;}/*** 获取左节点的数组下标* * @param i* @return*/private int left(int i) {return ((i + 1) << 1) - 1;}/*** 交换元素位置* * @param i* @param j*/private void swap(int i, int j) {int tmp = data[i];data[i] = data[j];data[j] = tmp;}/*** 获取堆中最小元素,即根元素* * @return*/public int getRoot() {return data[0];}/*** 替换根元素,并重新heapify* * @param root*/public void setRoot(int root) {data[0] = root;heapify(0);}
}

 

这篇关于小顶堆在Java中的一种优雅实现的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/268285

相关文章

Spring Boot + MyBatis Plus 高效开发实战从入门到进阶优化(推荐)

《SpringBoot+MyBatisPlus高效开发实战从入门到进阶优化(推荐)》本文将详细介绍SpringBoot+MyBatisPlus的完整开发流程,并深入剖析分页查询、批量操作、动... 目录Spring Boot + MyBATis Plus 高效开发实战:从入门到进阶优化1. MyBatis

SpringCloud动态配置注解@RefreshScope与@Component的深度解析

《SpringCloud动态配置注解@RefreshScope与@Component的深度解析》在现代微服务架构中,动态配置管理是一个关键需求,本文将为大家介绍SpringCloud中相关的注解@Re... 目录引言1. @RefreshScope 的作用与原理1.1 什么是 @RefreshScope1.

Java并发编程必备之Synchronized关键字深入解析

《Java并发编程必备之Synchronized关键字深入解析》本文我们深入探索了Java中的Synchronized关键字,包括其互斥性和可重入性的特性,文章详细介绍了Synchronized的三种... 目录一、前言二、Synchronized关键字2.1 Synchronized的特性1. 互斥2.

Spring Boot 配置文件之类型、加载顺序与最佳实践记录

《SpringBoot配置文件之类型、加载顺序与最佳实践记录》SpringBoot的配置文件是灵活且强大的工具,通过合理的配置管理,可以让应用开发和部署更加高效,无论是简单的属性配置,还是复杂... 目录Spring Boot 配置文件详解一、Spring Boot 配置文件类型1.1 applicatio

使用Sentinel自定义返回和实现区分来源方式

《使用Sentinel自定义返回和实现区分来源方式》:本文主要介绍使用Sentinel自定义返回和实现区分来源方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录Sentinel自定义返回和实现区分来源1. 自定义错误返回2. 实现区分来源总结Sentinel自定

Java中StopWatch的使用示例详解

《Java中StopWatch的使用示例详解》stopWatch是org.springframework.util包下的一个工具类,使用它可直观的输出代码执行耗时,以及执行时间百分比,这篇文章主要介绍... 目录stopWatch 是org.springframework.util 包下的一个工具类,使用它

Java进行文件格式校验的方案详解

《Java进行文件格式校验的方案详解》这篇文章主要为大家详细介绍了Java中进行文件格式校验的相关方案,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录一、背景异常现象原因排查用户的无心之过二、解决方案Magandroidic Number判断主流检测库对比Tika的使用区分zip

Java实现时间与字符串互相转换详解

《Java实现时间与字符串互相转换详解》这篇文章主要为大家详细介绍了Java中实现时间与字符串互相转换的相关方法,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录一、日期格式化为字符串(一)使用预定义格式(二)自定义格式二、字符串解析为日期(一)解析ISO格式字符串(二)解析自定义

opencv图像处理之指纹验证的实现

《opencv图像处理之指纹验证的实现》本文主要介绍了opencv图像处理之指纹验证的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学... 目录一、简介二、具体案例实现1. 图像显示函数2. 指纹验证函数3. 主函数4、运行结果三、总结一、

Java使用Curator进行ZooKeeper操作的详细教程

《Java使用Curator进行ZooKeeper操作的详细教程》ApacheCurator是一个基于ZooKeeper的Java客户端库,它极大地简化了使用ZooKeeper的开发工作,在分布式系统... 目录1、简述2、核心功能2.1 CuratorFramework2.2 Recipes3、示例实践3