堆排序

堆排序基本知识

基本介绍

堆是一个完全二叉树，因此我们可以利用节点的特性去使用一个数组模拟一颗完全二叉树：

  1. 下标为i的节点的左子节点的下标为i*2+1, 右子节点的下标为i*2+2
  2. 下标为i的节点的父节点的下标为(i-1)/2

建立堆的时间复杂度：O(log1) + O(log2) + … + O(logN) 近似于 O(N)，因此建立堆的时间复杂度为O(N)

堆有大根堆以及小根堆，没有规定堆中左子树的根必须大于(或小于)右子树的根。

堆排序的两个基本步骤：(具体说明看代码注释)
  1. 建堆，循环将数组中的每个数加入堆中（每次都需要heapInsert）
  2. 不断从堆的最后一个元素交换到堆的头部，然后将堆的长度减小1，再调整堆，每次都需要heapify
算法排序