堆排序

数据结构 堆

Heap（大顶堆）
1.complete Binary Tree
2.parent > children

关键点：完全二叉树可以用Array表示
建堆从右往左，从下往上建堆

一棵完全二叉树，从右往左，从下往上建堆

代码实现

用一维数组表示一棵树
因为他是完全二叉树，所以可以用数组表示

如何求父子节点， 利用完全二叉树的特点



实现：
每次找三个节点中最大的数，然后重新整理然后取最大值，再递归向下heapify
调整节点代码
这里假设子树已经是堆

const heapify = function(tree, i, n) {
  const c1 = 2 * i + 1
  const c2 = 2 * i + 2
  let max = i
  if (c1 < n && tree[max] < tree[c1]) {
    max = c1
  }
  if (c2 < n && tree[max] < tree[c2]) {
    max = c2
  }
  if (max !== i) {
    ;[tree[i], tree[max]] = [tree[max], tree[i]]
    // 递归， 防止换下来的节点比子树节点小
    heapify(tree, max, n)
  }
}

整体建堆
从最后一个节点的父节点开始（右下角）

const build_heap = function(tree) {
  const n = tree.length
  const last = n - 1
  const parent = Math.floor((last - 1) / 2)
  for (let i = parent; i >= 0; i--) {
    heapify(tree, i, n)
  }
}

堆排序 首尾交换，去除最后一个节点，然后再建堆

const heap_sort = function(tree) {
  build_heap(tree)
  const n = tree.length - 1
  for (let i = n; i >= 0; i--) {
    ;[tree[i], tree[0]] = [tree[0], tree[i]]
    heapify(tree, 0, i)
  }
}

整体代码

const log = console.log.bind(console)

const heapify = function(tree, i, n) {
  const c1 = 2 * i + 1
  const c2 = 2 * i + 2

  let max = i
  if (c1 < n && tree[max] < tree[c1]) {
    max = c1
  }
  if (c2 < n && tree[max] < tree[c2]) {
    max = c2
  }
  if (max !== i) {
    ;[tree[i], tree[max]] = [tree[max], tree[i]]
    heapify(tree, max, n)
  }
}
const build_heap = function(tree) {
  const n = tree.length
  const last = n - 1
  const parent = Math.floor((last - 1) / 2)
  for (let i = parent; i >= 0; i--) {
    heapify(tree, i, n)
  }
}
const heap_sort = function(tree) {
  build_heap(tree)
  const n = tree.length - 1
  for (let i = n; i >= 0; i--) {
    ;[tree[i], tree[0]] = [tree[0], tree[i]]
    heapify(tree, 0, i)
  }
}
const tree = [10, 99, 123, 2, 1, 4,-1, -100]
log(tree)
heap_sort(tree)
log(tree)