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

第一种方法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)中的一个,然后可以建立方程求解。

05-11 14:02