### Heap Sort

prefix knowlege: heap

• 步骤一: 构造大顶堆;
``````          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
}``````

• 由 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
}``````