建堆的时间复杂度 因为堆是完全二叉树，而满二叉树也是完全二叉树。此处为了简化，将采用满二叉树来证明。（时间复杂度本来看的就是近似值，所以多几个节点不会影响最终结果）：
假设树的高度为 
文章图片
：
文章图片
第则需要移动节点总的移动步数为：
文章图片
层：
文章图片
个节点，需要向下移动
文章图片
层
第
文章图片
层：
文章图片
个节点，需要向下移动
文章图片
层
第
文章图片
层：
文章图片
个节点，需要向下移动
文章图片
层
第
文章图片
层：
文章图片
个节点，需要向下移动
文章图片
层
……
第
文章图片
层：
文章图片
个节点，需要向下移动
文章图片
层
文章图片
①
文章图片
②
② - ① 错位相减：
文章图片
文章图片
文章图片
文章图片
文章图片
因此，建堆的时间复杂度为
文章图片
【《C语言杂俎》|证明堆排序的时间复杂度】
推荐阅读
- 指针|【发际线大作战】C++学习记录之用户自定义数据类型
- C++|set、map及AVL树
- 蓝桥杯|2018第九届蓝桥杯国赛JAVA B组真题解析（带源码及解析）
- 算法与数据结构的碰撞经典汇总|四平方和 剪枝+枚举 【蓝桥真题】（c++）
- Java每日一题|【蓝桥Java每日一题】——14.球会落何处（有趣模拟题）
- 蓝桥真题|【蓝桥真题3】蓝桥改革变难，想进国赛这些能力你可缺一不可
- 算法|开学季——经典计算机教材带你起飞！
- python|python数据结构-链表
- python|python 排序算法