附个人Java/C/C++/机器学习/算法与数据结构/前端/安卓/Python/程序员必读技术书
技术博客导航页:技术书栈
前面谈到了几种基础排序和快排,分别都用比较简单的方式给大家展示出来了。今天木了半天,眼看今天又要过去了,想了一下 肯定不怎么想学东西了 索性就抽出这点时间来跟整理一下堆排序吧。
很多人在看这个的时候肯定就很多人在思考了,到底什么是完全二叉树呢?
来我们先看一下对于完全二叉树的定义:
若设二叉树的深度为h,除第 h 层外,其它各层 (1~h-1) 的结点数都达到最大个数,第 h 层所有的结点都连续集中在最左边,这就是完全二叉树。
完全二叉树是由满二叉树而引出来的。对于深度为K的,有n个结点的二叉树,当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。
我们来简单的看一下吧:
额,硬要我说出什么是完全二叉树,我还是说不出来的,就是按照顺序整整齐齐的排列。
现在我们就从开始排序思想了,首先给定一个数组:[5,4 9,1 7,6,2],然后将该数组装入一个完全二叉树中:
如上图所示,红色的数字代表该项在项目的中的序号。
首先我们将目光关注在根结点处,此时我们发现,他的左孩子和右孩子分别是:2*i+1
2*i+2
。此时就出现了二叉树转换的思想:比较父节点和子节点的大小,将最大的节点放在父节点处,就这样一层一层进行递归。其代码如下:
function swap(tree,a,b){
let temp = tree[a];
tree[a] = tree[b];
tree[b] = temp;
}
function heapify(tree,n,i){
if(i>=n) return;
let leftChildNode = 2*i+1;
let rightChildNode = 2*i+2;
let max = i;
if(leftChildNode<n && tree[leftChildNode]>tree[max]){
max = leftChildNode;
}
if(rightChildNode < n&& tree[rightChildNode]>tree[max]){
max = rightChildNode;
}
if(max!==i){
swap(tree,i,max)
heapify(tree,n,max);
}
}
有了上面的代码之后,我们就可以来讲讲堆排序的核心思想了。首先我们用一组来解释过程
首先将指针拨向(n-1)/2(2)
处,然后通过上面的heapify来比较他和左右子节点的大小。
然后将指针拨向1处,然后通过上面的heapify比较大小。就这样1,4值做一下交换。
同理,就这样不断的偏移指针直到偏移到根结点。这样就找到了整棵树的最大值,即为根结点。
将根结点的值和树最后一个子节点的值做交换。
如图所示,将树的最后一个子节点给移出,此时剩下的值就组成了一个新的树。
以上就是堆排序最核心的思想了,其代码块为:
function findRootNode(tree,n){
let finalParentPoint = Math.floor((n-1-1)/2); // 数组从0开始 所以是从n-1-1开始,这里值得注意一下
for(let i = finalParentPoint;i>=0;i--){
heapify(tree,n,i);
}
}
通过前面的代码 我们就可以很容易的发现:前n项的最大值已经择出来了,而n-1项重新生成了一个无序的树,此时需要的只要考虑到的就只有前n-1项,就这样以此类推,终究得到一个排序好的数组。
具体的代码如下:
function heapSort(tree,n){
findRootNode(tree,n);
console.log(tree)
for(let i=n-1;i>=0;i--){
swap(tree,i,0);
heapify(tree,i,0);
}
}
其完整代码如下:
function swap(tree,a,b){
let temp = tree[a];
tree[a] = tree[b];
tree[b] = temp;
}
function heapify(tree,n,i){
if(i>=n) return;
let leftChildNode = 2*i+1;
let rightChildNode = 2*i+2;
let max = i;
if(leftChildNode<n && tree[leftChildNode]>tree[max]){
max = leftChildNode;
}
if(rightChildNode < n&& tree[rightChildNode]>tree[max]){
max = rightChildNode;
}
if(max!==i){
swap(tree,i,max)
heapify(tree,n,max);
}
}
function findRootNode(tree,n){
let finalParentPoint = Math.floor((n-1-1)/2); // 数组从0开始 所以是从n-1-1开始,这里值得注意一下
for(let i = finalParentPoint;i>=0;i--){
heapify(tree,n,i);
}
}
function heapSort(tree,n){
findRootNode(tree,n);
console.log(tree)
for(let i=n-1;i>=0;i--){
swap(tree,i,0);
heapify(tree,i,0);
}
}
关于排序这一块的代码展示,我想这就是我最后一章了。我在接下来的时间里面会重点来写一写,我在项目中遇到的问题(主要是安卓和前端两块)。而算法呢?一般都是我学不进去才花时间来写的,但是不写不知道 真的要把这个东西写清楚是比较麻烦的。特别是堆排序和无向图的最短距离这两章,不仅我写代码想了很久,如何表述清楚也一块也是花费了不少时间的。
本来我计划是今天还写一篇生活类的文章的,但是写完这篇文章都已经11点多了。额,写作不易,如果觉得对您有帮助,可以关注一下。我会定时分享优质内容的。
最后最后提到一句,欢迎大家点赞,关注我的个人博客,我会源源不断的输出高质量文章的。
附个人Java/C/C++/机器学习/算法与数据结构/前端/安卓/Python/程序员必读技术合集
书单导航页(点击右侧 即可打开个人博客):技术书栈
①【Java】从入门到进阶带你走上大牛之路技术书大全(珍藏版):
②【算法数据结构+acm】从入门到进阶技术书大全(珍藏版):
③【数据库】从入门到进阶技术书大全(珍藏版):
④【Web前端】从入门到进阶技术书大全(珍藏版):
⑤【python】从入门到进阶技术书大全(珍藏版):
文章浏览阅读4.4k次,点赞2次,收藏16次。写这篇文章的由来是因为后边要用这个工具,但是由于某些原因有部分小伙伴和童鞋们可能不会安装此工具,为了方便小伙伴们和童鞋们的后续学习和不打击他们的积极性,因为80%的人都是死在工具的安装这第一道门槛上,这门槛说高也不高说低也不是太低。所以就抽时间水了这一篇文章。_eclipse安装教程
文章浏览阅读4.1w次,点赞12次,收藏193次。小编为大家收集了11个web前端开发,大企业实战项目案例+5W行源码!拿走玩去吧!1)小米官网项目描述:首先选择小米官网为第一个实战案例,是因为刚开始入门,有个参考点,另外站点比较偏向目前的卡片式设计,实现常见效果。目的为学者练习编写小米官网,熟悉div+css布局。学习资料的话可以加下web前端开发学习裙:600加上610再加上151自己去群里下载下。项目技术:HTML+CSS+Div布局2)迅雷官网项目描述:此站点特效较多,所以通过练习编写次站点,学生可以更多练习CSS3的新特性过渡与动画的实_前端项目实战案例
文章浏览阅读73次。素数,不同的质数,各种各样的问题总是遇到的素数。以下我们来说一下求素数的一种比較有效的算法。就是筛法。由于这个要求得1-n区间的素数仅仅须要O(nloglogn)的时间复杂度。以下来说一下它的思路。思路:如今又1-n的数字。素数嘛就是除了1和本身之外没有其它的约数。所以有约数的都不是素数。我们从2開始往后遍历,是2的倍数的都不是素数。所以我们把他们划掉然后如...
文章浏览阅读532次,点赞9次,收藏14次。探索Keras DCGAN:深度学习中的创新图像生成项目地址:https://gitcode.com/jacobgil/keras-dcgan在数据驱动的时代,图像生成模型已经成为人工智能的一个重要领域。其中,Keras DCGAN 是一个基于 Keras 的实现,用于构建和训练 Deep Convolutional Generative Adversarial Networks(深度卷积生...
文章浏览阅读116次。今天在搭建springcloud项目时,发现如上错误,顺便整理一下这个异常:1. mapper.xml的命名空间(namespace)是否跟mapper的接口路径一致<mapper namespace="com.baicun.springcloudprovider.mapper.SysUserMapper">2.mapper.xml接口名是否和mapper.java接..._spring-could org.apache.ibatis.binding.bindingexception: invalid bound state
文章浏览阅读1.1k次。四种高效数据库设计思想——提高查询效率:设计数据库表结构时,我们首先要按照数据库的三大范式进行建立数据。1. 1NF每列不可拆分2. 2NF确保每个表只做一件事情3. 3NF满足2NF,消除表中的依赖传递。三大范式的出现是在上世纪70年代,由于内存资源比较昂贵,所以严格按照三大范式进行数据库设计。而如今内存变得越来越廉价,在考虑效率和内存的基础上我们可以做出最优选择以达到最高效率。_数据库为什么能提高效率
文章浏览阅读302次。一. HTML标签分类1.根据标签个数分类。 单标签:只有一个标签。 <br>, <hr>,<img>,<meta>, 实现一个特定的功能。 双标签:既有开始标签,也有结束标签。 Html,head,Body,title,h1~h6,p,a,ul,li,ol,strong,em。2.根据标签特性分类(网页效果)。 2.1行属性..._ol是单标记还是双标记
文章浏览阅读1.6k次。应用程序在启动和运行的时候往往需要读取一些配置信息,配置基本上伴随着应用程序的整个生命周期,比如:数 据库连接参数、启动参数等。配置主要有以下几个特点:配置是独立于程序的只读变量配置对于程序是只读的,程序通过读取配置来改变自己的行为,但是程序不应该去改变配置配置伴随应用的整个生命周期配置贯穿于应用的整个生命周期,应用在启动时通过读取配置来初始化,在运行时根据配置调整行为。比如:启动时需要读取服务的端口号、系统在运行过程中需要读取定时策略执行定时任务等。配置可以有多种加载方式常见的有程序内部_基于配置是什么意思
文章浏览阅读170次。Glib库实现了一个非常重要的基础类--GObject,这个类中封装了许多我们在定义和实现类时经常用到的机制: 引用计数式的内存管理 对象的构造与析构 通用的属性(Property)机制 Signal的简单使用方式 很多使用GObject..._
文章浏览阅读6.3k次,点赞2次,收藏9次。在 golang 中若写定时脚本,有两种实现。一、基于原生语法组装func DocSyncTaskCronJob() { ticker := time.NewTicker(time.Minute * 5) // 每分钟执行一次 for range ticker.C { ProcTask() }}func ProcTask() { log.Println("hello world")}二、基于 github 中封装的 cron 库实现package taskimport (_golang 定时任务
文章浏览阅读2.1k次。 来源:http://blog.csdn.net/clever101/archive/2008/10/18/3096049.aspx 声明:本文章是我整合网上的资料而成的,其中的大部分文字不是我所为的,我所起的作用只是归纳整理并添加我的一些看法。非常感谢引用到的文字的作者的辛勤劳动,所参考的文献在文章最后我已一一列出。 对关注性能的程序开发人员而言,一个好的计时部件既是益友,也_vc 通过线程和 sleep 获取精准时间
文章浏览阅读58次。公司突然说要进行wap开发了,以前从没了解过,但我却异常的兴奋,因为可以学习新东西了,呵呵,我们大家一起努力吧。首先说说环境的搭建。可以把.wml的文件看做是另一种的html进行信息的展示,但并不是所有的浏览器都支持,好用的有Opera,还有WinWap。编写wml文件语法比较严格,不好的是我还没有找到好的提示工具,就先用纯文本吧。我找到了一个很好的学习网站:http://w3sc..._winwap学习