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

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

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

既然小顶堆已经实现出来,那么同理大顶堆也顺理成章实现出来,只需稍微改动几个关键部分的代码。

/*** 大顶堆/最大堆实现* * @author stephenshen**/
public class MaxHeap {// 堆得存储结构:数组private int[] data;/*** 构造方法:传入一个数组,并转换为一个最大堆* * @param data*/public MaxHeap(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 biggest = i;// 存在左子节点,且左子节点的值大于当前节点的值if (l < data.length && data[l] > data[i])biggest = l;// 存在右子节点,且右子节点的值大于当前节点的值if (r < data.length && data[r] > data[i])biggest = r;// 左右结点的值都小于根节点,直接returnif (i == biggest)return;// 将最大值与当前节点互换位置swap(i, biggest);// 从之前最大值节点位置重新堆化heapify(biggest);}/*** 获取右节点的数组下标* * @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/268286

相关文章

Spring AI 实现 STDIO和SSE MCP Server的过程详解

《SpringAI实现STDIO和SSEMCPServer的过程详解》STDIO方式是基于进程间通信,MCPClient和MCPServer运行在同一主机,主要用于本地集成、命令行工具等场景... 目录Spring AI 实现 STDIO和SSE MCP Server1.新建Spring Boot项目2.a

spring security 超详细使用教程及如何接入springboot、前后端分离

《springsecurity超详细使用教程及如何接入springboot、前后端分离》SpringSecurity是一个强大且可扩展的框架,用于保护Java应用程序,尤其是基于Spring的应用... 目录1、准备工作1.1 引入依赖1.2 用户认证的配置1.3 基本的配置1.4 常用配置2、加密1. 密

Spring Boot 集成 Solr 的详细示例

《SpringBoot集成Solr的详细示例》:本文主要介绍SpringBoot集成Solr的详细示例,本文通过实例代码给大家介绍的非常详细,感兴趣的朋友一起看看吧... 目录环境准备添加依赖配置 Solr 连接定义实体类编写 Repository 接口创建 Service 与 Controller示例运行

Spring Cloud GateWay搭建全过程

《SpringCloudGateWay搭建全过程》:本文主要介绍SpringCloudGateWay搭建全过程,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐... 目录Spring Cloud GateWay搭建1.搭建注册中心1.1添加依赖1.2 配置文件及启动类1.3 测

Java如何将文件内容转换为MD5哈希值

《Java如何将文件内容转换为MD5哈希值》:本文主要介绍Java如何将文件内容转换为MD5哈希值的实现方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录Java文件内容转换为MD5哈希值一个完整的Java示例代码代码解释注意事项总结Java文件内容转换为MD5

Spring Boot拦截器Interceptor与过滤器Filter深度解析(区别、实现与实战指南)

《SpringBoot拦截器Interceptor与过滤器Filter深度解析(区别、实现与实战指南)》:本文主要介绍SpringBoot拦截器Interceptor与过滤器Filter深度解析... 目录Spring Boot拦截器(Interceptor)与过滤器(Filter)深度解析:区别、实现与实

解决Java异常报错:java.nio.channels.UnresolvedAddressException问题

《解决Java异常报错:java.nio.channels.UnresolvedAddressException问题》:本文主要介绍解决Java异常报错:java.nio.channels.Unr... 目录异常含义可能出现的场景1. 错误的 IP 地址格式2. DNS 解析失败3. 未初始化的地址对象解决

C#实现访问远程硬盘的图文教程

《C#实现访问远程硬盘的图文教程》在现实场景中,我们经常用到远程桌面功能,而在某些场景下,我们需要使用类似的远程硬盘功能,这样能非常方便地操作对方电脑磁盘的目录、以及传送文件,这次我们将给出一个完整的... 目录引言一. 远程硬盘功能展示二. 远程硬盘代码实现1. 底层业务通信实现2. UI 实现三. De

SpringBoot后端实现小程序微信登录功能实现

《SpringBoot后端实现小程序微信登录功能实现》微信小程序登录是开发者通过微信提供的身份验证机制,获取用户唯一标识(openid)和会话密钥(session_key)的过程,这篇文章给大家介绍S... 目录SpringBoot实现微信小程序登录简介SpringBoot后端实现微信登录SpringBoo

Java中的StringUtils.isBlank()方法解读

《Java中的StringUtils.isBlank()方法解读》:本文主要介绍Java中的StringUtils.isBlank()方法,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑... 目录所在库及依赖引入方法签名方法功能示例代码代码解释与其他方法的对比总结StringUtils.isBl