Repository navigation
Expand file tree
/
Copy pathMaxHeap.js
More file actions
126 lines (124 loc) · 3.81 KB
/
Copy pathMaxHeap.js
File metadata and controls
126 lines (124 loc) · 3.81 KB
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
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
/*
* 最大堆
* 堆的本质是一种树形结构
*/
module.exports.maxHeap = class MaxHeap {
constructor() {
this.data = [];
this.count = 0;
}
// 初始化堆
// 传递一个数组,通过heapify快速生成堆
init(arr) {
if(arr instanceof Array) {
this.data = arr;
this.count = arr.length;
this.heapify(arr);
}
}
// 通过函数快速生成最大堆
heapify(arr) {
var count = arr.length;
for(var i = Math.floor(count/2); i >= 0; i--) {
this.shiftDown(i);
}
}
// 返回堆中的元素个数
size() {
return this.count;
}
// 判断堆中是否为空
isEmpty() {
return this.count === 0;
}
// 提升元素,但插入新元素的时候，判断该元素是不是最大值
// 索引从0开始，所以i元素的左子元素为2*i+1,右子元素为2*i+2,i元素的父元素为(i-1)/2
shiftUp(k) {
while(k >= 0 && this.data[Math.floor((k-1)/2)] < this.data[k]) {
// 如果子元素大于父元素,交换位置
this.swap(this.data, Math.floor((k-1)/2), k);
k = Math.floor((k-1)/2);
}
}
// 向最大堆中插入一个新的元素
insert(element) {
this.data.push(element);
this.count = this.data.length;
// 判断新插入的元素是不是最大值
this.shiftUp(this.count-1);
}
// 从最大堆取出元素后，需要重新获得最大值，放到堆的顶部
shiftDown(k) {
while(2*k+1 <= this.count-1) {
// 左子元素对应的索引
var j = 2 * k + 1;
if(j+1 <= this.count-1 && this.data[j+1] > this.data[j]) {
// 判断当前右子元素是否存在，值是否大于子左元素
j++;
}
// 如果父元素大于子元素，则不用交换，保持原来位置
if(this.data[k] >= this.data[j]) break;
this.swap(this.data, k, j);
k = j;
}
}
// 优化shiftDown,使用赋值的方式取代不断的swap
// 优化思路借鉴插入排序的优化思路
shiftDownII(k) {
// 先保持k索引对应的值
var t = this.data[k];
while(2*k+1 <= this.count-1) {
var j = 2 * k + 1;
if(j+1 <= this.count-1 && this.data[j+1] > this.data[j]) {
j++;
}
if(t > this.data[j]) break;
arr[k] = arr[j];
k = j;
}
// 最后再赋值
this.data[k] = e;
}
// 从最大堆中取出堆顶元素，即堆中所存储的最大数据
extractMax() {
if(this.count <=0) return;
var ret = this.data[0];
this.swap(this.data, 0, this.count-1);
this.count--;
// 更新堆顶
this.shiftDown(0);
return ret;
}
// 获取堆的最大值
getMax() {
return this.data[0];
}
// 交换数据
swap(arr, a, b) {
var t = arr[a];
arr[a] = arr[b];
arr[b] = t;
}
}
// 堆排序1
// 时间复杂度O(nlogn)
module.exports.heapSort1 = function heapSort1(arr) {
var maxHeap = new exports.maxHeap();
for(var i = 0; i < arr.length; i++) {
maxHeap.insert(arr[i]);
}
for(var i = arr.length-1; i >= 0; i--) {
arr[i] = maxHeap.extractMax();
}
}
// 堆排序2
// 借助heapify过程创建堆
// 此时创建堆的过程时间复杂度为O(n),将所有元素依次从堆中取出来，时间复杂度为O(nlogn)
// 总体时间复杂度仍为O(nlogn)，但优化了创建堆的时间
module.exports.heapSort2 = function heapSort2(arr) {
var maxHeap = new exports.maxHeap();
maxHeap.init(arr);
for(var i = arr.length-1; i >= 0; i--) {
arr[i] = maxHeap.extractMax();
}
}