curTain

经过一轮轮的秋招面试,体会到数据结构的重要性,打算系统的学习一遍

api 设计

实现堆

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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
class Heap {
constructor(){
// 储存堆中的元素
this.items = []
// 记录堆中元素的个数
this.n = 0
}

// 判断堆中索引 i 处的元素是否小于索引 j 处的元素
less( i=0, j=0 ){
return this.items[i] < this.items[j]
}
// 交换堆中索引 i 和 j 处的值
swop( i=0, j=0 ){
[ this.items[i], this.items[j] ] = [ this.items[j], this.items[i] ]
}
// 删除堆中最大的元素,并返回这个最大的元素
deleteMax(){
let max = this.items[ 1 ]
// 交换索引 1 处的元素与最大索引处的元素,让完全二叉树的最右侧元素变为根节点
this.swop( 1, this.n )
// 删除最大元素
this.items[ this.n ] = null
// 元素个数 -1
this.n --
// 通过下沉调整堆,让堆重新有序
this.sink( 1 )
return max
}

// 往堆中插入一个元素
insert( value ){
this.items[ ++this.n ] = value
this.swim( this.n )
}

// 使用上浮算法,使索引 k 处的元素能在堆中处于正确的位置
swim( k=0 ){
// 父级链进行比较
while( k > 1 ){
// 比较当前节点和其父节点
if( this.less( Math.floor( k/2 ), k ) ){
this.swop( Math.floor( k/2 ), k )
}
k = Math.floor( k/2 )
}
}

// 使用下沉算法,使索引 k 处的元素能在堆中处于正确的位置
sink( k=0 ){
// 通过循环不断对比当前 k 节点和其左子节点 2*k 以及 右子节点 2*k+1 处中较大值的元素
while( 2*k <= this.n ){
// 获取当前节点的子节点中较大的节点
let max // 记录较大节点所在的索引
if( 2*k + 1 <= this.n ){
if( this.less( 2*k, 2*k + 1 ) ){
max = 2*k + 1
} else {
max = 2*k
}
} else {
max = 2*k
}
// 比较当前节点和较大节点的值
if( this.less( max, k ) ){
break
}
// 交换 k 索引处的值和 max 做阴处的值
this.swop( k, max )

// 变换 k 的值
k = max
}
}
}

// 测试
let myHeap = new Heap()
myHeap.insert(1)
myHeap.insert(2)
myHeap.insert(3)
myHeap.insert(4)
myHeap.insert(5)
myHeap.insert(6)

let res = null
while( (res = myHeap.deleteMax()) !== null ){
console.log( res )
}

实现堆排序的堆

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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
 // 堆排序
class HeapSort {
// 判断 heap 堆中索引 i 处的元素是否小于索引 j 处的元素
less( heap=[], i=0, j=0 ){
return heap[i] < heap[j]
}
// 交换 heap 堆中 i 索引和 j 索引的值
swop( heap=[], i=0, j=0 ){
[ heap[i], heap[j] ] = [ heap[j], heap[i] ]
}
// 根据原数据 source,构造出堆 heap
createHeap( source=[], heap=[] ){
// 把 source 中的元素拷贝到 heap 中,heap 是一个无序堆
// 将第一个元素空出来
heap.push( "", ...source )
// 对堆中的元素做下沉调整(从长度的一半开始下沉)
for( let i = Math.floor( source.length / 2 ); i > 0; i -- ){
this.sink( heap, i, heap.length-1 )
}
}

sink( heap=[], target=0, range=0 ){
while( 2*target <= range ){
// 找出当前节点较大的子节点
let max
if( 2*target+1 <= range ){
if( this.less( heap, 2*target, 2*target+1 ) ){
max = 2*target+1
} else {
max = 2*target
}
} else {
max = 2*target
}
// 比较当前节点的值和较大节点的值
if( !this.less( heap, target, max ) ){
break
}
this.swop( heap, target, max )
target = max
}
}
sort( source=[] ){
// 构建堆
let newHeap = []
this.createHeap( source, newHeap )
console.log( "变换后的堆:", newHeap )
// 定义一个变量,记录为排序的元素中最大的索引
let n = newHeap.length - 1
// 通过循环,交换1索引处的元素和排序的元素中最大的索引的元素
while( n > 1 ){
// 交换元素
this.swop( newHeap, 1, n )
// 排除交换后最大元素所在的索引,让他不要参与下沉
n --
// 对索引1处的元素进行下沉调整
this.sink( newHeap, 1, n )
}
// 把 heap 中的数据复制到原 source 中
console.log( "交换后的堆:", newHeap )
newHeap.shift()
source.length = 0
source.push( ...newHeap )
}
}


// 测试
// 待排序的数组
let sourceArr = [ "S","O","R","T","E","X","A","M","P","L","E" ]
// 通过 heapSort 对数组进行排序
let heapSort = new HeapSort()
heapSort.sort( sourceArr )

console.log( sourceArr )

 评论