当前位置： 首页 > 编程日记 > 正文

算法导论Java实现-构建MaxHeap

编程日记 2025-01-20 11:40:00 

  1. package lhz.algorithm.chapter.six; 
  2. /** 
  3.  * “构建堆”，《算法导论》6.3章节 Building a heap 
  4.  * 利用之前实现的<code>MaxHeapify</code>算法，构建max-heap。 
  5.  * 伪代码： 
  6.  * BUILD-MAX-HEAP(A) 
  7.  * 1 heap-size[A] ← length[A] 
  8.  * 2 for i ← ⌊length[A]/2⌋ downto 1 
  9.  * 3 do MAX-HEAPIFY(A, i) 
  10.  * @author lihzh(苦逼coder) 
  11.  * 本文地址：http://mushiqianmeng.blog.51cto.com/3970029/737557
  12.  */ 
  13. public class BuildMaxHeap { 
  14.      
  15.     private static int[] input = new int[] { 4, 1, 3, 2, 16, 9, 10, 14, 8, 7 }; 
  16.     private static int heapSize = input.length; 
  17.  
  18.     public static void main(String[] args) { 
  19.         buildMaxHeap(); 
  20.         //打印数组 
  21.         printArray(); 
  22.     } 
  23.      
  24.     /** 
  25.      * 构造max-heap 
  26.      * 复杂度：《算法导论》原文分析如下： 
  27.      * Each call to MAX-HEAPIFY costs O(lg n) time, and there are O(n) such calls.  
  28.      * Thus,the running time is O(n lg n).  
  29.      */ 
  30.     private static void buildMaxHeap() { 
  31.         //从树的深层逆序，构造max-heap,正好每次均可满足 
  32.         //MaxHeapify算法的前提，即所有子二叉树已经是max-heap 
  33.         for (int i = heapSize/2; i > 0; i--) { 
  34.             maxHeapify(input, i); 
  35.         } 
  36.     } 
  37.      
  38.     /** 
  39.      * MaxHeap，调整算法，前提是假设所有的子二叉树已经是max-heap。 
  40.      * 复杂度： 
  41.      * 因为：T (n) ≤ T(2n/3) + Θ(1) 
  42.      * 所以有：T (n) = O(lgn) 
  43.      * @param array 
  44.      * @param index 
  45.      */ 
  46.     private static void maxHeapify(int[] array, int index) { 
  47.         int l = index * 2; 
  48.         int r = l + 1; 
  49.         int largest; 
  50.         //如果左叶子节点索引小于堆大小，比较当前值和左叶子节点的值，取值大的索引值 
  51.         if (l <= heapSize && array[l-1] > array[index-1]) { 
  52.             largest = l; 
  53.         } else { 
  54.             largest = index; 
  55.         } 
  56.         //如果右叶子节点索引小于堆大小，比较右叶子节点和之前比较得出的较大值，取大的索引值 
  57.         if (r <= heapSize && array[r-1] > array[largest-1]) { 
  58.             largest = r; 
  59.         } 
  60.         //交换位置，并继续递归调用该方法调整位置。 
  61.         if (largest != index) { 
  62.             int temp = array[index-1]; 
  63.             array[index-1] = array[largest-1]; 
  64.             array[largest-1] = temp; 
  65.             maxHeapify(array,largest); 
  66.         } 
  67.     } 
  68.      
  69.     private static void printArray() { 
  70.         for (int i : input) { 
  71.             System.out.print(i + " "); 
  72.         } 
  73.     } 
  74. } 
图示：


     本文转自mushiqianmeng 51CTO博客，原文链接：http://blog.51cto.com/mushiqianmeng/737557，如需转载请自行联系原作者




 https://www.dkcj.cn/info/37110.html
 
相关文章：
哲学家就餐问题c语言_哲学家就餐问题的一种Python解决方案
哲学家就餐问题一直是多线程同步问题的经典案例&#xff0c;本文中展示了多线程竞争共享资源带来的死锁问题&#xff0c;并介绍了一种简单的解决方案。哲学家就餐问题哲学家最擅长的就是思考和吃饭 &#xff0c;当他们感觉累的时候&#xff0c;就会拿起一双筷子去吃盘子里的寿司…
编程日记2025/01/20 11:30:00
倒计时1天，2018 AI开发者报名通道即将关闭（附参会提醒）
参加 2018 AI开发者大会&#xff0c;请点击 ↑↑↑随着 AI 逐渐转为各大科技巨头的战略主战场&#xff0c;人工智能技术亦是长立风口&#xff0c;向阳而生。越来越多的发展趋势表明&#xff0c;未来的人工智能将逐步迈入广泛普及阶段&#xff0c;继而深入影响人类日常的生产生活…
编程日记2025/01/20 11:20:00
Linux安全检查方法
检查系统密码文件,查看文件修改日期 [rootfedora ~]# ls -l /etc/passwd 查看passwd文件中有哪些特权用户 [rootfedora ~]# awk -F: $30 {print $1} /etc/passwd 查看系统里有没有空口令帐户 awk -F: length($2)0 {print $1} /etc/shadow 检查系…
编程日记2025/01/20 11:10:00
Ubuntu Server 12.04下cobbler + dnsmasq +tftpd-hpa的安装配置（四）
四、自定义 kickstart 文件 Kickstart最早是RedHat公司用来自动部署RedHat操作系统的&#xff0c;通过Kickstart配置文件&#xff0c;通常安装过程中需要交互输入的信息就都可以自动应答。 通过Kickstart安装操作系统一般是这样几个步骤&#xff1a; Create a kickstart file. …
编程日记2025/01/20 11:00:00
AI 技术实力图谱全解析！2018 中国 AI 开发者大会重磅来袭
【2018 AI 开发者大会图文直播】 11 月 8 日&#xff0c;由中国专业 IT 社区 CSDN 与硅谷 AI 社区 AICamp 联合出品的 2018 中国 AI 开发者大会&#xff08;AI NEXTCon&#xff09; 在北京拉开帷幕&#xff0c;近百位中美顶尖 AI 专家、知名企业代表、逾千名 AI 开发者&#x…
编程日记2025/01/20 10:50:00
sql的不等于条件优化_SQL优化案例（2）：OR条件优化
随后上一篇文章《 SQL优化案例(1)&#xff1a;隐式转换》的介绍&#xff0c;此处内容围绕OR的优化展开。在MySQL中&#xff0c;同样的查询条件&#xff0c;如果变换OR在SQL语句中的位置&#xff0c;那么查询的结果也会有差异&#xff0c;在多个复杂的情况下&#xff0c;可能会带…
编程日记2025/01/20 10:40:00
所有 SAP 现在开设的标准课程
下面是 SAP 中国的教育培训首页&#xff0c;里面有 SAP 最新最完整的培训教育计划。 http://www30.sap.com/china/services/education/index.epx 从中可以看出&#xff0c;随着 SAP 的发展&#xff0c;BC4xx 系列课程已经发生了很大改变&#xff0c;取消了 BC404、BC406&#x…
编程日记2025/01/20 10:30:00
动态展开所有_库存与市场需求之间如何“动态”共舞？库存计划动态模型构建分享...
库存(Stock)是用来提高交货速度、缓冲需求到单高峰的常用手段&#xff0c;通过按库存生产(MTS)的方法&#xff0c;用储备库存来满足客户需求、并按一定规则补货&#xff0c;无需等待生产周期&#xff0c;可极快地交付。相比按订单生产(MTO)的模式&#xff0c;采用安全库存可以有…
编程日记2025/01/20 10:20:00
Linux下DNS简单部署（主从域名服务器）
一、DNS简介 DNS&#xff08;Domain Name System&#xff09;&#xff0c;域名系统&#xff0c;因特网上作为域名和IP地址相互映射的一个分布式数据库&#xff0c;能够使用户更方便的访问互联网&#xff0c;而不用去记住能够被机器直接读取的IP数串。通过主机名&#xff0c;最终…
编程日记2025/01/20 10:10:00
Neurala与CSDN宣布战略合作，将一站式AI平台BrainBuilder带给中国开发者
11 月 8 日&#xff0c;美国人工智能创新企业 Neurala 与中国开发者社区 CSDN 联合宣布&#xff0c;正式成为战略合作伙伴&#xff0c;通过双方的合作&#xff0c;将 BrainBuilder 平台提供给中国的更多开发者和教育培训机构。Brain Builder 是 Neurala 开发的一站式 AI 平台。…
编程日记2025/01/20 10:00:00
使用idea创建springboot项目并打成war包发布到weblogic上...
部署tomcat也是类似的&#xff0c;但是需要注意项目配置的路径&#xff0c;或者直接将项目放到webapp的ROOT目录下。 使用工具&#xff1a;intelliJ IDEA2016.3&#xff0c; jdk1.8 &#xff0c;weblogic12 一 使用idea创建springboot项目 File-》New -》Project 选择jdk版本…
编程日记2025/01/20 09:50:00
cs架构嵌入bs_CS与BS架构区别、比较、及现状与趋势分析
一、简介 CS即Client/Server(客户机/服务器)结构&#xff0c;C/S结构在技术上很成熟&#xff0c;它的主要特点是交互性强、具有安全的存取模式、网络通信量低、响应速度快、利于处理大量数据。但是该结构的程序是针对性开发&#xff0c;变更不够灵活&#xff0c;维护和管理的难…
编程日记2025/01/20 09:40:00
大数据的“平民化”、“流动化”、“商业化”推动企业升级与转型
CSDN 出品的《2018-2019 中国人工智能产业路线图》V2.0 版已经重磅面世&#xff01; V1.0 版发布以来&#xff0c;我们有幸得到了诸多读者朋友及行业专家的鼎力支持&#xff0c;在此表示由衷感谢。此次 V2.0 版路线图进行了新一轮大升级&#xff0c;内容包括 3 大 AI 前沿产业趋…
编程日记2025/01/20 09:30:00
APIPA是什么？
<?xml:namespace prefix o ns "urn:schemas-microsoft-com:office:office" />APIPA&#xff08;Automatic Private IP Addressing&#xff0c;自动专用IP寻址自动专用IP寻址&#xff09;&#xff0c;是一个DHCP故障转移机制。当DHCP服务器出故障时&#xff…
编程日记2025/01/20 09:20:00
birt报表表格边框_手把手教你五步制作出一张领导驾驶舱报表
领导驾驶舱报表是一款为企业内部领导及相关高管提供企业数据指标分析的报表&#xff0c;用来实时反映企业的运行状况&#xff0c;将企业管理决策提升到一个新的高度。今天小编用亿信华辰的亿信ABI给大家实际演示&#xff0c;通过5个步骤就可以刷刷刷“变”出漂亮的领导驾驶舱&a…
编程日记2025/01/20 09:10:00
Web的现状：网页性能提升指南
互联网发展非常迅速&#xff0c;所以我们创造了Web平台。通常 我们会忽视连通性等问题&#xff0c;但用户们却不会视而不见 。一瞥万维网的现状&#xff0c;可以发现我们并没有用同情心、变通意识去构建它&#xff0c;更不要说性能了。 所以&#xff0c;今天的Web是什么状态呢?…
编程日记2025/01/20 09:00:00
[导入]ExtJs 2.0 弹窗事例
网站: JavaEye 作者: ppkosd 链接&#xff1a;http://ppkosd.javaeye.com/blog/133004 发表时间: 2007年10月18日 责任不是你应该做的事情,而是你必须做的事情 -- ppkosd 这个EXT 2.0 的例子 讲的是怎么样用aspserver和ext2.0构建弹窗效果! 服务器部分&#xff1a; 代码va…
编程日记2025/01/20 08:50:00
双十一报名截止，决赛在即！AI Challenger2018极客峰会免费抢票！
第二届“AI Challenger 全球AI挑战赛”各赛道竞赛经过两个多月的激烈角逐&#xff0c;报名将于北京时间2018年11月11日23:59:59正式截止&#xff0c;随即进入决赛阶段&#xff0c;最终每个竞赛的TOP 5团队将进入12月18、19日在北京举办的总决赛答辩及颁奖礼&#xff0c;角逐超过…
编程日记2025/01/20 08:40:00
取值范围_从int取值范围谈起
int取值范围我们在面试过程中&#xff0c;或者在准备面试过程中&#xff0c;可能会遇到这样一个问题&#xff1a;Java中int的取值范围是什么&#xff1f;这个问题比较常见&#xff0c;也很简单&#xff0c;相信大部分Java开发人员都可以快速答上来&#xff1a;[ , ]即使不能马上…
编程日记2025/01/20 08:30:00
MonoRail学习笔记五：定制服务实现自定义功能
在上一篇MonoRail学习笔记四&#xff1a;MonoRail基本流程分析中我提到&#xff0c;MonoRail中可以自定义一些服务。比如可以定义自己的Url解析类&#xff0c;来实现http://localhost:***/index.rails等http://localhost:***/*.rails的效果。具体步骤如下&#xff1a;1、修改we…
编程日记2025/01/20 08:20:00
我的第一个vb实例--红楼梦测试小程序
http://files.cnblogs.com/gengxiaochao/hlmtest.rar 转载于:https://www.cnblogs.com/gengxiaochao/archive/2007/11/26/973072.html
编程日记2025/01/20 08:10:00
2018 AI产业投融资分析：热钱涌向何处，谁的“寒冬”将至？
AI科技大本营按&#xff1a;本篇内容来自由 CSDN 出品的《2018 中国人工智能产业路线图》V2.0 版中 1.4 章投融资分析篇&#xff0c;通过对各大 AI 行业进行相关数据分析&#xff0c;我们尽可能勾勒出中国 AI 产业发展现状&#xff0c;并对行业未来做出趋势判断。产业路线图 2.…
编程日记2025/01/20 08:00:01
mvc的宿舍管理系统源码 基于jsp_[源码和文档分享]基于JSP的MVC框架实现的图书推荐系统展示平台网站...
推荐系统是目前互联网中最常见的一种智能产品形式。由于网络中信息量的快速增长以及图书出版行业出版量的攀升&#xff0c;人们需要一种办法&#xff0c;来解决信息过载的问题。此外&#xff0c;用户访问网络是为了获取信息&#xff0c;但并不是所有的访问都有很强的目的性&…
编程日记2025/01/20 07:50:00
Ms Sql Server 基本管理脚本(1)
/* *登录帐户管理*/--授予Windows账号test访问数据库的权限exec sp_grantlogin teacher-jin\test--拒绝Windows账号test访问数据库的权限exec sp_denylogin teacher-jin\test--回收Windows账号test访问数据库的权限exec sp_revokelogin teacher-jin\test--授予Windows组users访…
编程日记2025/01/20 07:40:00
配置Android开发环境（fedora)
配置Android开发环境&#xff08;fedora) 最进看见google的Android&#xff0c;体会了下&#xff0c;按照官网上的配置了下&#xff0c;后编了个Hello Android结果发现没能传到模拟器上&#xff1b;于是在windows xp上试了下&#xff0c;没问题。那么为什么会有问题呢&#xff…
编程日记2025/01/20 07:30:01
精选Python开源项目Top10！
作者 | MyBridge译者 | Linstancy整理 | Jane出品 | AI科技大本营【导读】过去一个月里&#xff0c;我们对近 250 个 Python 开源项目进行了排名&#xff0c;并挑选出热度前 10 的项目。这份清单的平均 github star 数量高达 1140&#xff0c;涵盖了包括性能分析、提取 PDF 中的…
编程日记2025/01/20 07:20:00
全局声明宏定义_Rust语言：元编程，强大的宏系统，菜鸟到高手进阶的必经之路...
编程语言的宏操作&#xff0c;在C和C早期就已经存在。宏可以将重复的代码用更简短的宏函数替换&#xff0c;编译过程中再展开&#xff0c;使得代码编写的更简洁。Rust提供了两种宏&#xff0c;分别是声明宏和过程宏。声明宏的形式和C的宏替换类似&#xff0c;区别在于Rust会对宏…
编程日记2025/01/20 07:10:00
SpringBoot 1024行代码 - 系统监控工具 Actuator简介
前言 在生产环境中&#xff0c;我们比较关心任意时刻一个JVM的运行情况。SpringBoot为我们提供了一个方便的功能模块Actuator。只要简单几步就可以为我们的应用添加查询系统各项指标的功能。 准备工作 完成SpringBoot 1024行代码 - Getting Started&#xff08;一个简单的web应…
编程日记2025/01/20 07:00:00
新一代宽带路由器—Vigor防火墙路由器
华盖科技隆重推出新一代宽带路由器—Vigor防火墙路由器上网行为管理时代的来临一、网络信息乱七八糟 计算机病毒泛滥、******造成信息丢失&#xff1b;不健康的文字、图片、广告&#xff0c;带有淫秽、、暴力等有害信息的网站、不健康的网络信息影响了网络环境。如何保证信息的…
编程日记2025/01/20 06:50:00
2018 中国AI人才大调查：14张图表解读他们来自何处，又将去往何方？
AI科技大本营按&#xff1a;本篇内容来自由 CSDN 出品的《2018 人工智能产业路线图》V2.0 版中 1.6 章人才分析篇&#xff0c;通过对相关 AI 人才各维度的数据分析&#xff0c;我们尽可能勾勒中国 AI 人才发展的全景面貌。产业路线图 2.0 完整版我们将很快提供读者下载&#xf…
编程日记2025/01/20 06:40:00