-
-
Notifications
You must be signed in to change notification settings - Fork 254
/
MinHeap.ts
126 lines (121 loc) · 2.75 KB
/
MinHeap.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
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
export interface HeapWrapper<T> {
key: number,
timestamp : number,
value: T
}
export class MinHeap<T> {
private heap: HeapWrapper<T>[];
private timestamp : number;
constructor() {
this.heap = [];
this.timestamp=0;
}
lessThan(a:HeapWrapper<T>,b:HeapWrapper<T>){
return a.key==b.key?a.timestamp<b.timestamp:a.key<b.key;
}
shift(v: number) {
this.heap = this.heap.map(({ key, value,timestamp }) => ({ key: key + v, value,timestamp }));
}
len() {
return this.heap.length;
}
push(value: T,key : number) {
this.timestamp+=1;
const loc = this.len();
this.heap.push({value,timestamp : this.timestamp,key});
this.updateUp(loc);
}
pop(): HeapWrapper<T> {
if (this.len() == 0) {
throw new Error("no element to pop");
}
const top = this.heap[0];
if (this.len() > 1) {
this.heap[0] = this.heap.pop() as HeapWrapper<T>;
this.updateDown(0);
} else {
this.heap.pop();
}
return top;
}
find(v: T): HeapWrapper<T> | null {
for (let i = 0; i < this.len(); i++) {
if (v == this.heap[i].value) {
return this.heap[i];
}
}
return null;
}
remove(v: T) {
let index = null;
for (let i = 0; i < this.len(); i++) {
if (v == this.heap[i].value) {
index = i;
}
}
if (index === null) { return false; }
if (this.len() > 1) {
let last = this.heap.pop() as HeapWrapper<T>;
if (last.value != v) { // if the last one is being removed, do nothing
this.heap[index] = last;
this.updateDown(index);
}
return true;
} else {
this.heap.pop();
}
return true;
}
private parentNode(x: number): number {
return Math.floor((x - 1) / 2);
}
private leftChildNode(x: number): number {
return 2 * x + 1;
}
private rightChildNode(x: number): number {
return 2 * x + 2;
}
private existNode(x: number): boolean {
return x >= 0 && x < this.heap.length;
}
private swap(x: number, y: number) {
const t = this.heap[x];
this.heap[x] = this.heap[y];
this.heap[y] = t;
}
private minNode(numbers: number[]) {
const validnumbers = numbers.filter(this.existNode.bind(this));
let minimal = validnumbers[0];
for (const i of validnumbers) {
if (this.lessThan(this.heap[i],this.heap[minimal])) {
minimal = i;
}
}
return minimal;
}
private updateUp(x: number) {
if (x == 0) {
return;
}
const parent = this.parentNode(x);
if (this.existNode(parent) && this.lessThan(this.heap[x],this.heap[parent])) {
this.swap(x, parent);
this.updateUp(parent);
}
}
private updateDown(x: number) {
const leftChild = this.leftChildNode(x);
const rightChild = this.rightChildNode(x);
if (!this.existNode(leftChild)) {
return;
}
const m = this.minNode([x, leftChild, rightChild]);
if (m != x) {
this.swap(x, m);
this.updateDown(m);
}
}
debugPrint() {
console.log(this.heap);
}
}