CLRS笔记6：堆排序

终于搞明白堆排序了，汗一个

先上代码：

def heapify(a, idx, size)
  left_idx = 2 * idx + 1
  right_idx = 2 * idx + 2
  bigger_idx = idx
  bigger_idx = left_idx if left_idx < size && a[left_idx] > a[idx]
  bigger_idx = right_idx if right_idx < size && a[right_idx] > a[bigger_idx]
  if bigger_idx != idx
    a[idx], a[bigger_idx] = a[bigger_idx], a[idx]
    heapify(a, bigger_idx, size)
  end
end

def build_heap(a)
  last_parent_idx = a.length / 2 - 1
  i = last_parent_idx
  while i >= 0
    heapify(a, i, a.size)
    i = i - 1
  end
end

def heap_sort(a)
  return a if a.size <= 1
  size = a.size
  build_heap(a)
  while size > 0
    a[0], a[size-1] = a[size-1], a[0]
    size = size - 1
    heapify(a, 0, size)
  end
  return a
end

a = [1,5,3,6,4,3,2,7,9,0,8,0,10]
p heap_sort(a)

算法原理：
利用二叉树，先将一个数组构建成一个“最大堆”，保证对每个节点i，它的相邻子节点left和right都<=i
这时根节点就是最大的数，将它和最后一个节点互换位置
然后从根节点开始与相邻的子节点比较大小，如果left或right比它大，则互换位置，称为“下移”，直到第n-1个节点，这一轮“下移”之后根节点成为除了最后一个节点之外最大的数，将它和倒数第二个节点互换位置
。。。
循环直到所有节点做完“下移”操作，这时数组已经从小到大排好序了

关键：
有两点：
1，先构建“最大堆”，从最后一个节点的父节点开始做“下移”，直到根节点
2，每次“下移”结束后不能将最大值根节点从数组中删除，只能跟最后一个节点互换位置，这样是为了保证二叉树的结构不变，即还是一个“最大堆”，所以堆排序又称为“in place sort”

时间复杂度：
一个长度为n的数组，用二叉树来表示的话共有lgn层
对节点i，比较它相邻的left节点和right节点并做“下移”操作的时间为Θ(1)
可以用数学归纳法来证明heapsort的时间复杂度为Θ(nlogn)
1，初始化构建“最大堆”的时间为O(nlgn)，不影响结果(实际上为O(n))
2，可以知道对n=3,6,f(n) < nlgn,
而f(2n) = f(n) + nlg(2n)
        < nlgn + n(1+lgn)
        = 2nlgn + n
        < 2n(lgn + 1)
        = 2nlg2n
所以fn = Θ(nlgn)