参考 堆排序中两种建堆方法的比较

第一种方法HeapInsert

它可以假定我们事先不知道有多少个元素，通过不断往堆里面插入元素进行调整来构建堆。

它的大致步骤如下：

1. 首先增加堆的长度，在最末尾的地方加入最新插入的元素。

2. 比较当前元素和它的父结点值，如果比父结点值大，则交换两个元素，否则返回。

3. 重复步骤2.

这种插入建堆的时间复杂度是O(NlogN)

第二种方法Heapify

从最后一个非叶子节点一直到根结点进行堆化的调整。如果当前节点小于某个自己的孩子节点（大根堆中），那么当前节点和这个孩子交换。Heapify是一种类似下沉的操作，HeapInsert是一种类似上浮的操作。

这种建堆的时间复杂度是O(N)

怎么找到第一个非叶子节点

参考博客中根节点在数组中的索引为1，所以第一个非叶子节点的计算公式为: last_non_leaf = arr.length/2。

如果根节点在数组中的索引为0，那么第一个非叶子节点的计算公式为: last_non_leav = (arr.length - 2)/2

可以设最后一个非叶子节点位置为x，那么最后一个叶子节点一定是(2x+1) 或者(2x+2)中的一个，然后可以建立方程求解。

最新文章

1. IOS自定义日历控件的简单实现(附思想及过程)
2. HTML5上传图片到ASP.NET.MVC
3. CXF发布webService服务以及客户端调用
4. exam help
5. P142-1
6. 4.python中的用户交互
7. [转]C/C++中的memset
8. JSONObject和JSONArray
9. 斯坦福ML公开课笔记15—隐含语义索引、神秘值分解、独立成分分析
10. java 时间
11. [帖子收集]环境光遮蔽（Ambient Occlusion）
12. Redis各种数据结构性能数据对比和性能优化实践
13. Qt Creator编译运行成功，但是显示系统找不到指定的文件(比如urlmon.dll动态链接库)
14. java类中获取ServletContext的方法
15. 05_Javascript进阶第二天
16. SpringBoot（四）：banner的控制
17. echarts切换tab时，第一个图表显示，第二个图表不显示的解决办法
18. SHELL 脚本小技巧
19. 小程序https请求，http网站升到https
20. 看到的一个关于C++能力分级的描述

热门文章

1. Redis: 缓存过期、缓存雪崩、缓存穿透、缓存击穿(热点)、缓存并发(热点)、多级缓存、布隆过滤器
2. SQL--合计函数（Aggregate functions）:avg,count,first,last,max,min,sum
3. sql--index 索引
4. 比特(bit)和字节(Byte)
5. java实现spark常用算子之count
6. MySQL中自定义排序
7. js判断变量是否为undefined
8. Django框架——基础之模型系统（ORM的介绍和字段及字段参数）
9. JS常用自定义函数总结
10. 4G漏洞