附个人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】从入门到进阶技术书大全(珍藏版):
文章浏览阅读1.1w次,点赞7次,收藏34次。vue-grid-layout的使用、实例、遇到的问题和解决方案_vue-grid-layout
文章浏览阅读218次。然后连接一个数据源,就会在下面自动产生一个添加附件的组件。把这个控件复制粘贴到页面里,就可以单独使用来上传了。插入一个“编辑”窗体。_powerapps点击按钮上传附件
文章浏览阅读264次。(1) Abstraction (抽象)(2) Polymorphism (多态)(3) Inheritance (继承)(4) Encapsulation (封装)_"object(cnofd[\"ofdrender\"])十条"
文章浏览阅读133次。删除node_modules,重新npm install看是否成功。在 package.json 文件中的 scripts 中加入。修改你的第三方库的bug等。然后目录会多出一个目录文件。_修改 node_modules
文章浏览阅读883次。【代码】【】kali--password:su的 Authentication failure问题,&sudo passwd root输入密码时Sorry, try again._password: su: authentication failure
文章浏览阅读1w次,点赞13次,收藏97次。整理5个优秀的微信小程序开源项目。收集了微信小程序开发过程中会使用到的资料、问题以及第三方组件库。_微信小程序开源模板
文章浏览阅读128次。Centos7最简搭建NFS服务器_centos7 搭建nfs server
文章浏览阅读1.2k次,点赞2次,收藏3次。前言mybatis在持久层框架中还是比较火的,一般项目都是基于ssm。虽然mybatis可以直接在xml中通过SQL语句操作数据库,很是灵活。但正其操作都要通过SQL语句进行,就必须写大量的xml文件,很是麻烦。mybatis-plus就很好的解决了这个问题。..._mybaitis-plus ruledataobjectattributemapper' and 'com.picc.rule.management.d
文章浏览阅读325次。EECE 1080C / Programming for ECESummer 2022Laboratory 4: Global Functions PracticePlagiarism will not be tolerated:Topics covered:function creation and call statements (emphasis on global functions)Objective:To practice program development b_eece1080c
文章浏览阅读53次。被同机房早就1年前就学过的东西我现在才学,wtcl。设要求的数为\(x\)。设当前处理到第\(k\)个同余式,设\(M = LCM ^ {k - 1} _ {i - 1}\) ,前\(k - 1\)个的通解就是\(x + i * M\)。那么其实第\(k\)个来说,其实就是求一个\(y\)使得\(x + y * M ≡ a_k(mod b_k)\)转化一下就是\(y * M ...
文章浏览阅读1.3k次。首先,问题是如何出现的?晚上复查代码,发现一个activity没有调用自己的ondestroy方法我表示非常的费解,于是我检查了下代码。发现再finish代码之后接了如下代码finish();System.exit(0);//这就是罪魁祸首为什么这样写会出现问题System.exit(0);////看一下函数的原型public static void exit (int code)//Added ..._android 手动杀死app,activity不执行ondestroy
文章浏览阅读894次。Q: SylixOS 版权是什么形式, 是否分为<开发版税>和<运行时版税>.A: SylixOS 是开源并免费的操作系统, 支持 BSD/GPL 协议(GPL 版本暂未确定). 没有任何的运行时版税. 您可以用她来做任何 您喜欢做的项目. 也可以修改 SylixOS 的源代码, 不需要支付任何费用. 当然笔者希望您可以将使用 SylixOS 开发的项目 (不需要开源)或对 SylixOS 源码的修改及时告知笔者.需要指出: SylixOS 本身仅是笔者用来提升自己水平而开发的_select函数 导致堆栈溢出 sylixos