Heap Sort

prefix knowlege: heap

题目: 给定数组 [5, 2, 7, 3, 1, 8, 4], 使用堆排序对其进行升序排列。

• 步骤一: 构造大顶堆;

5
        ↙   ↘ convert
     2         7
          |
    因为子节点 7 大于 5, 因此作 convert, 结果如下
          ↓

          7
        ↙   ↘
     2         5
          |
    依此类推, 构造出大顶堆。
          ↓

           8
        ↙     ↘
     3          7
  ↙    ↘      ↙   ↘
2        1  5       4

• 步骤二: 取出顶部元素, 将数组末尾元素移到顶部(目的是为了保持移除了顶部元素后的数组长度减少 1);
• 步骤三: 如果存在顶部元素的子元素大于顶部元素的情形, 对调它们(维持 max heap);

8
        ↙     ↘
     3          7
  ↙    ↘      ↙   ↘
2        1  5       4
          |
  取出顶部 8, 将数组末尾元素 4 移到顶部
          ↓

           4
        ↙     ↘ (对调)
     3          7
  ↙    ↘      ↙
2        1  5
          |
  如果存在顶部元素的子元素大于顶部元素的情形, 对调它们, 重新构造 max heap.
          ↓

           7
        ↙     ↘
     3          4
  ↙    ↘      ↙
2        1  5
          |
  重复上述 3 个步骤, 直到堆中的元素为空

下面来实现上述步骤:

var heap_sort = function(arr) {
  const result = []
  let material = arr

  while (material.length > 0) {
    const maxHeapArr = builtMaxHeap(material)
    result.unshift(maxHeapArr[0])
    maxHeapArr[0] = maxHeapArr[maxHeapArr.length - 1]
    material = maxHeapArr.slice(0, maxHeapArr.length - 1)
  }

  return result
}

// input: [5, 2, 7, 3, 1, 8, 4]
// output: to build big heap [8, 3, 7, 2, 1, 5, 4]
var builtMaxHeap = function(arr) {
  let parent, compareChild
  for (let i = 0; i < arr.length; i++) {
    parent = Math.floor((i - 1) / 2)
    compareChild = i
    while (parent >= 0) {
      if (arr[parent] < arr[compareChild]) {
        swap(arr, parent, compareChild)
        compareChild = parent
        parent = Math.floor((compareChild - 1) / 2)
      } else {
        parent = -1
      }
    }
  }
  return arr
}

// swap two value in arr
var swap = function(arr, pointOne, pointTwo) {
  const tmp = arr[pointOne]
  arr[pointOne] = arr[pointTwo]
  arr[pointTwo] = tmp
}

理想情况下, 堆排序时间复杂度应为 nlogn, 空间复杂度应为 1, 上述实现的代码中没有达到这一复杂度的。参考社区代码后重写:

• 由 len 控制执行时机;
• 对 arr 进行操作不引入额外变量;

var len
var heap_sort = function(arr) {
  buildMaxHeapify(arr)

  while (len > 1) {
    swap(arr, len - 1, 0)
    len--
    keepMaxHeapify(arr, 0)
  }

  return arr
}


/**
 * to build max heapify from bottom to top;
 * the last subscript's parent subscript is Math.floor((len - 1) / 2)
 */
var buildMaxHeapify = function(arr) {
  len = arr.length

  for (let i = Math.floor((len - 1) / 2); i >= 0; i--) {
    keepMaxHeapify(arr, i)
  }
}

/**
 * to keep max heap
 */
var keepMaxHeapify = function(arr, i) {
  const left = 2 * i + 1
  const right = 2 * i + 2
  let maxSubscript = i

  if (left < len && arr[left] > arr[maxSubscript]) {
    maxSubscript = left
  }

  if (right < len && arr[right] > arr[maxSubscript]) {
    maxSubscript = right
  }

  if (maxSubscript !== i) {
    swap(arr, maxSubscript, i)
    keepMaxHeapify(arr, maxSubscript)
  }
}

/**
 * swap two value in arr
 */
var swap = function(arr, pointOne, pointTwo) {
  const tmp = arr[pointOne]
  arr[pointOne] = arr[pointTwo]
  arr[pointTwo] = tmp
}