堆和堆排序
akong 2019-01-08 12:42:51 堆排序
堆排序,了解一哈~
# 堆&堆排序
# 优先队列
普通队列:先进先出;后进后出;和时间相关
优先队列:出对顺序和入队顺序无关,和优先级相关 动态
- 医院急救
- 操作系统优先队列
- 网络请求
操作: 入队 出队(依次取出优先级最高的元素)
入队 | 出队 | |
---|---|---|
普通数组 | O(1) | O(n) |
顺序数组 | O(n) | O(1) |
堆 | O(logN) | O(logn) |
对于总共N个请求,使用普通数组或者顺序数组,最差情况O(n^2),使用堆则稳定在 O(nlogn)
# 堆-二叉堆
堆是树形结构,最经典的是二叉堆
堆这种数据结构在动态的数据维护上很又优势
# 定义
二叉堆满足两个条件
- 堆中某个节点的值总是不大于(不小于)其父节点的值
- 前者对应的是大根堆(最大堆)
- 后者对应的是小根堆(最小堆)
- 二叉堆总是一个完全二叉树(其前n-1层必须被填满,第n层也要从左到右顺序填满)来实现
实现
因为其是完全二叉树,所以我们用数组来存储二叉堆。
已大根堆为例:
- 子左节点的序列号为父节点的2倍
- 子右节点的序列号为父节点的2倍+1
已知子节点序号i: 父节点的序号parent (i) = i/2 js语言要对结果向下取整
已知父节点序号i: 子节点的序号 left child (i) = 2*i
right child (i) = 2*i + 1
# Js实现堆-代码
// 大根堆
function MaxHeap() {
this.data = []
this.count = 0
}
MaxHeap.prototype.swap = function(arr,i,j) {
let t = arr[i]
arr[i] = arr[j]
arr[j] = t
}
MaxHeap.prototype.size = function () {
return this.count
}
MaxHeap.prototype.isEmpty = function() {
return this.count == 0
}
/*
堆的插入:
- 插入尾部 count++
- 进入shiftUp
- 比较是否符合大根堆的特点,不符合就进行调整
*/
MaxHeap.prototype.insert = function(item) {
// 传统数组[0..count-1] 表示堆的数组 [1..count] 所以这里是count+1
this.data[this.count + 1] = item
this.count++
this.shiftUp(this.count)
}
MaxHeap.prototype.shiftUp = function(k) {
while(k>1&&this.data[Math.floor(k / 2)]<this.data[k]) {
this.swap(this.data, k, Math.floor(k / 2))
k = Math.floor(k / 2)
}
}
/* 从堆中取出一个元素:
- 只能取根节点元素,对于最大堆来说,取出的就是优先级最大的元素
- 最后一个元素放到根元素的位置 保证其是完全二叉树
- 进入shifDown,调换位置,保证其是大根堆(最大堆)
*/
MaxHeap.prototype.extractMax = function () {
if (this.count>0) {
let res = this.data[1]
this.swap(this.data,1,this.count)
this.count--
this.shiftDown(1)
return res
} else {
throw new Error('堆为空')
}
}
MaxHeap.prototype.shiftDown = function (k) {
while(this.count>=2*k) {
let j = 2*k
if (j+1 <=this.count && this.data[j+1]>this.data[j]){
j++
}
if (this.data[k]>=this.data[j]) {
break
}
this.swap(this.data,k,j)
k=j
}
}
//-----------test-------------
let maxHeap = new MaxHeap()
for (let i = 1;i<=5;i++) {
// Math.floor(Math.random() * (rangeR - rangeL + 1)) + rangeL
var num = Math.floor(Math.random() * 101)
maxHeap.insert(num)
}
console.log(maxHeap.data)
while (!maxHeap.isEmpty()) {
console.log(maxHeap.extractMax());
};
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
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
# 堆排序
# 一代
根据上面堆的实现 我们可以轻松完成一个堆排序
let MaxHeap = require('./01-js实现堆')
function heapSort(arr) {
let maxHeap = new MaxHeap()
for(let i=0;i<arr.length;i++) {
maxHeap.insert(arr[i])
}
for(let i=arr.length - 1;i>=0;i--) {
arr[i] = maxHeap.extractMax()
}
return arr
}
let arr = [10, 9, 8, 7, 6, 5, 4, 3, 2, 1]
console.log(heapSort(arr))
// [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
2
3
4
5
6
7
8
9
10
11
12
13
14
15
效率不是很完美 我们进行优化
# 二代
对于一代的优化,主要就是将数组转化为堆的过程,有一种更好的方法,称为Heapify
之前的大根堆构造函数
function MaxHeap() {
this.data = []
this.count = 0
}
1
2
3
4
2
3
4
我们改造一下Maxheap
构造函数:
// --------二代------------
/*
heapify: 将整个数组构建成堆
对于一棵完全二叉树,第一个非叶子节点的索引值=Math.floor(元素个数/2)
从第一个非叶子节点开始递减,依次shiftDown
*/
function MaxHeap(arr) {
if(arr&&Object.prototype.toString.call(arr) === '[object Array]') {
let i
let len = arr.length
this.data = []
for(i=0;i<len;i++) {
this.data[i+1] = arr[i]
}
this.count = len
for(i=Math.floor(this.count/2);i>=1;i--) {
this.shiftDown(i)
}
} else {
this.data = []
this.count = 0
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
排序算法:
/*
一代:将n个元素逐个插入到一个空堆中,算法复杂度是O(nlogn)
二代:heapify的过程,直接舍弃了n/2个元素,算法复杂度为O(n)
*/
function heapSort(arr) {
let maxHeap = new MaxHeap(arr)
for (let i = arr.length - 1; i >= 0; i--) {
arr[i] = maxHeap.extractMax()
}
return arr
}
let arr = [10, 9, 8, 7, 6, 5, 4, 3, 2, 1]
console.log(heapSort(arr))
1
2
3
4
5
6
7
8
9
10
11
12
13
2
3
4
5
6
7
8
9
10
11
12
13
# 三代
主要改进是思想是: 原地进行堆排序,不依靠额外的空间
因为直接从数组开始调整堆结构,所以这里我的树要从0开始索引
parent(i) = (i - 1)/2
left child (i) = 2*i + 1
right child (i) = 2*i + 2
最后一个非叶子节点的索引(count - 1)/2
//------------三代----------------------------
/*
原地堆排序:无需额外的空间,直接在原数组上进行原地的堆排序
树从0开始索引
parent(i) = (i - 1)/2
left child (i) = 2*i + 1
right child (i) = 2*i + 2
最后一个非叶子节点的索引(count - 1)/2
*/
function heapSort(arr) {
// 从第一个非叶子节点开始,依次递减,shiftDown后,数组变为最大堆
for(let i = Math.floor((arr.length-1)/2);i>=0;i--){
__shiftDown(arr,arr.length,i)
}
// 将数组的第一个数(数组中最大的数) 和最后一个元素交换位置,这样就保证最的元素在后面
// count-- 再把堆重新shifDown成最大堆 在进行上面操作
for(let i=arr.length-1;i>0;i--){
swap(arr,i,0)
__shiftDown(arr,i,0)
}
return arr
}
function __shiftDown(arr,n,k) {
while(2*k+1<n) {
let j = 2*k+1
if(j+1<n&&arr[j+1]>arr[j]){
j++
}
if(arr[k]>=arr[j]) {
break
}
swap(arr,k,j)
k = j
}
}
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
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