堆是一个完全二叉树,因此我们可以利用节点的特性去使用一个数组模拟一颗完全二叉树:
- 下标为i的节点的左子节点的下标为
i*2+1
, 右子节点的下标为i*2+2
- 下标为i的节点的父节点的下标为(i-1)/2
基本介绍
堆是一个完全二叉树,因此我们可以利用节点的特性去使用一个数组模拟一颗完全二叉树:
i*2+1
, 右子节点的下标为i*2+2
建立堆的时间复杂度:O(log1) + O(log2) + … + O(logN) 近似于 O(N),因此建立堆的时间复杂度为O(N)
堆有大根堆以及小根堆,没有规定堆中左子树的根必须大于(或小于)右子树的根。
堆排序的两个基本步骤:(具体说明看代码注释)