-
Notifications
You must be signed in to change notification settings - Fork 0
/
maxHeap.ts
79 lines (67 loc) · 2.05 KB
/
maxHeap.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
import { heap, iHeap } from './heap';
class MaxHeap<T> implements iHeap<T> {
private heap: heap<T> = new Array();
public getLeftChild = (index: number) => index * 2 + 1;
public getRightChild = (index: number) => index * 2 + 2;
public getParent = (index: number) => Math.floor((index - 1) / 2);
public peek = () => this.heap[0];
public dump = (): heap<T> => this.heap;
public insert2(item: T): void {
this.heap.push(item);
let index = this.heap.length - 1;
let parentIndex = this.getParent(index);
while (index > 0 && this.heap[index] > this.heap[parentIndex]) {
this.swap(index, parentIndex);
index = parentIndex;
}
}
public insert(item: T): T {
this.heap.push(item);
let index = this.heap.length - 1;
let parentIndex = this.getParent(index);
const traverse = (index: number) => {
if (index > 0 && this.heap[index] > this.heap[parentIndex]) {
this.swap(index, parentIndex);
traverse(parentIndex)
}
}
traverse(index);
return item;
}
public extractMax() {
const root = this.heap.shift();
this.heap.unshift(this.heap[this.heap.length - 1]);
this.heap.pop();
this.heapify(0);
return root;
}
public heapify(index: number) {
let left = this.getLeftChild(index);
let right = this.getRightChild(index);
let length = this.heap.length;
let smallest = index;
if (left < length && this.heap[smallest] < this.heap[left]) {
smallest = left;
}
if (right < length && this.heap[smallest] < this.heap[right]) {
smallest = right;
}
if (smallest != index) {
this.swap(smallest, index);
this.heapify(smallest);
}
}
public swap(a: number, b: number): void {
[this.heap[a], this.heap[b]] = [this.heap[b], this.heap[a]]
}
}
const heap = new MaxHeap<number>();
heap.insert2(33);
heap.insert2(4);
heap.insert2(31);
heap.insert2(6);
// MIN [85,64,67,51,59,42,48]
// MAX [36, 23, 10]
console.log(`Dump ${heap.dump()}`);
console.log(`ExtractMax ${heap.extractMax()}`);
console.log(`Dump ${heap.dump()}`);