-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathHeap.html
88 lines (71 loc) · 2.5 KB
/
Heap.html
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
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8">
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<title>Document</title>
</head>
<body>
<script>
class MinHeap{
constructor(){
this.heap = [];
}
insert(element){
this.heap.push(element);
this.bubbleUp();
}
bubbleUp(){
let index = this.heap.length - 1;
while(index > 0){
let parentIndex = Math.floor((index - 1) / 2);
if(this.heap[parentIndex] <= this.heap[index]) break;
[this.heap[parentIndex], this.heap[index]] = [this.heap[index], this.heap[parentIndex]];
index = parentIndex;
}
}
extractMin(){
if(this.heap.length === 0) return null;
if(this.heap.length === 1) return this.heap.pop();
const min = this.heap[0];
this.heap[0] = this.heap.pop();
this.bubbleDown();
return min;
}
bubbleDown(){
let index = 0;
const length = this.heap.length;
let smallest = index;
while(true){
let leftChildIndex = 2 * index + 1;
let rightChildIndex = 2 * index + 2;
if(leftChildIndex < length && this.heap[leftChildIndex] < this.heap[smallest]){
smallest = leftChildIndex;
}
if(rightChildIndex < length && this.heap[rightChildIndex] < this.heap[smallest]){
smallest = rightChildIndex;
}
if(smallest === index) break;
[this.heap[index], this.heap[smallest]] = [this.heap[smallest], this.heap[index]]
index = smallest
}
}
peek(){
if(this.heap.length === 0) return null;
return this.heap[0]
}
}
const minHeap = new MinHeap();
minHeap.insert(3)
minHeap.insert(4)
minHeap.insert(7)
minHeap.insert(9)
minHeap.insert(10)
minHeap.insert(1)
minHeap.insert(0)
console.log(minHeap.peek());
console.log(minHeap.extractMin())
console.log(minHeap.peek());
</script>
</body>
</html>