-
Notifications
You must be signed in to change notification settings - Fork 1
/
heap-sort.ts
46 lines (39 loc) · 1.29 KB
/
heap-sort.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
/**
* 堆排序
* 使用大顶堆实现升序排序(小顶堆实现降序排序)
* 原址排序
* 时间复杂度:O(n*lgn)
*
* 基于大顶堆的性质:堆顶元素总是整个堆中最大的。
*
* 步骤:
* 1. 将堆顶元素和堆尾元素互换,同时堆元素数量减 1(即换到堆尾的元素不再算作堆元素);
* 2. 对新堆顶执行 heapify;
* 3. 循环执行步骤1、2,直到堆中只剩一个元素(最后一个元素不需要交换了);
* 其实就是不断从数组剩余元素中取最大的,从数组末尾自右向左依次排列。
*/
import { Heap, Value } from '../data-structure/heap'
class SortHeap extends Heap {
/**
* 执行堆排序
*/
public sort() {
let tmp: Value
while (this._size > 1) {
// 将堆顶和堆尾元素交换
tmp = this.data[1]
this.data[1] = this.data[this._size]
this.data[this._size] = tmp
// 堆元素数减一
this._size--
// heapify
this.heapify(1)
}
// 因为建堆的时候我们向数组开头添加了一个元素,需要删掉
this.data.shift()
}
}
function heapSort(arr: Value[]) {
(new SortHeap(arr, true)).sort()
}
export { heapSort, Value }